# US 8,751,448 B1 · State-based directing of segments in a multinode deduplicated storage system > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,751,448 B1 - Document ID: US8751448B1 - Status: Granted - Kind: B1 - Application number: 12/653,313 - Filed: 2009-12-11 - Granted: 2014-06-10 - Earliest claimed: 2009-12-11 - Assignees: EMC Corporation - Applicants: Frederick Douglis; Philip Shilane; R. Hugo Patterson - Inventors: Frederick Douglis; Philip Shilane; R. Hugo Patterson - Web page: https://patentgrep.com/patent/US8751448B1 ## 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 3/0608: {Saving storage space on storage systems} - G06F 3/0641: {De-duplication techniques} - G06F 3/0689: {Disk arrays, e.g. RAID, JBOD} - G06F 16/137: {Hash-based (content-based indexing of textual data G06F16/31)} - G06F 16/1744: {using compression, e.g. sparse files} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A system for directing for storage includes a processor and a memory. The processor is configured to determine a segment overlap for each of a plurality of nodes. The processor is further configured to determine a selected node of the plurality of nodes based at least in part on the segment overlap for each of the plurality of nodes and based at least in part on a selection criteria. The memory is coupled to the processor and configured to provide the processor with instructions. ## Claims ### Claim 1 A system for directing for storage, comprising: a processor configured to: segment input data comprising a data stream, a data block, or a data file into a plurality of segments; group at least some of the plurality of segments into a super segment including by: determining, for each of at least some of the plurality of segments, whether a hash value computed for a segment of the plurality of segments that is associated with a segment boundary and for the segment boundary meet one or more super segment boundary criteria; and in the event that the one or more super segment boundary criteria are met, setting a super segment boundary at the segment boundary that is associated with the segment; and determine, for a first node of a plurality of nodes, a segment overlap for the super segment by determining whether each of the at least some of the plurality of segments comprising the super segment is stored on the first node based at least in part on a probabilistic data structure, wherein the segment overlap comprises a value representative of a number of the plurality of segments comprising the super segment that have been previously stored on the first node of the plurality of nodes; determine a selected node of the plurality of nodes including by comparing the segment overlap determined for at least the first node to a threshold, wherein the threshold is a value that is based at least in part on a total number of the plurality of segments comprising the super segment and a total number of nodes in the plurality of nodes; and a memory coupled to the processor and configured to provide the processor with instructions. ### Claim 2 (depends on 1) The system as in claim 1, wherein determining the segment of the plurality of segments comprises determining segment boundaries based at least in part on a hash of a content of the segment. ### Claim 3 (depends on 1) The system as in claim 1, wherein grouping at least some of the plurality of segments into at the super segment further includes determining super segment boundaries based at least in part on a hash of a content of the super segment. ### Claim 4 (depends on 3) The system as in claim 3, wherein the hash comprises a hash over an initial portion of the content of the super segment. ### Claim 5 (depends on 3) The system as in claim 3, wherein grouping the at least some of the plurality of segments into the super segment further includes determining super segment boundaries based at least in part on a minimum length and/or a maximum length. ### Claim 6 (depends on 1) The system as in claim 1, further comprising directing the super segment to the selected node. ### Claim 7 (depends on 1) The system as in claim 1, wherein the threshold is proportional to a number of segments in the super segment. ### Claim 8 (depends on 1) The system as in claim 1, wherein the threshold is inversely proportional to a number of nodes in the plurality of nodes. ### Claim 9 (depends on 1) The system as in claim 1, wherein in the event that the segment overlap does not determine the selected node, determining the selected node based at least in part on a content of the super segment. ### Claim 10 (depends on 9) The system as in claim 9, wherein determining is based on a hash of a content of a segment of the super segment. ### Claim 11 (depends on 1) The system as in claim 1, wherein in the event that the segment overlap does not determine the selected node, determining the selected node based at least in part on a loading of a node. ### Claim 12 (depends on 11) The system as in claim 11, wherein determining the selected node is based at least in part on a least loaded node of the plurality of nodes. ### Claim 13 (depends on 1) The system as in claim 1, wherein determining the selected node is based at least in part on the segment overlap weighted by a loading of a node. ### Claim 14 (depends on 13) The system as in claim 13, wherein the weighting comprises one or more of the following: a weight proportional to an inverse of a node loading, a weight proportional to an inverse of a node loading squared, a weight value set to zero in the event that a node load exceeds a relative loading threshold, a weight described using a linear function, and a weight described using a non-linear function. ### Claim 15 (depends on 14) The system as in claim 14, wherein the threshold comprises one of the following: a predetermined threshold, a threshold that varies over time, or a threshold that is adaptive. ### Claim 16 A method for directing for storage, comprising: segmenting input data comprising a data stream, a data block, or a data file into a plurality of segments; grouping at least some of the plurality of segments into at least one super segment including by: determining, for each of at least some of the plurality of segments, whether a hash value computed for a segment associated with a segment boundary and the segment boundary meet one or more super segment boundary criterion; and setting a super segment boundary at a segment boundary associated with a segment determined to meet the super segment boundary criterion; determining, using a processor, for a first node of a plurality of nodes, a segment overlap for the at least one super segment including by determining whether each of at least a subset of the plurality of segments comprising the super segment is stored on the first node based at least in part on a probabilistic data structure, wherein the segment overlap comprises a value representative of a number of the plurality of segments comprising the at least one super segment that have been previously stored on the first node of the plurality of nodes; and determining a selected node of the plurality of nodes including by comparing the segment overlap determined for at least the first node to a threshold, wherein the threshold is a value that is based at least in part on a total number of the plurality of segments comprising the at least one super segment and a total number of nodes in the plurality of nodes. ### Claim 17 A computer program product for directing for storage, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for: segmenting input data comprising a data stream, a data block, or a data file into a plurality of segments; grouping at least some of the plurality of segments into at least one super segment including by: determining, for each of at least some of the plurality of segments, whether a hash value computed for a segment associated with a segment boundary and the segment boundary meet one or more super segment boundary criterion; and setting a super segment boundary at a segment boundary associated with a segment determined to meet the super segment boundary criterion; determining, for a first node of a plurality of nodes, a segment overlap for the at least one super segment including by determining whether each of at least a subset of the plurality of segments comprising the super segment is stored on the first node based at least in part on a probabilistic data structure, wherein the segment overlap comprises a value representative of a number of the plurality of segments comprising the at least one super segment that have been previously stored on the first node of the plurality of nodes; and determining a selected node of the plurality of nodes including by comparing the segment overlap determined for at least the first node to a threshold, wherein the threshold is a value that is based at least in part on a total number of the plurality of segments comprising the at least one super segment and a total number of nodes in the plurality of nodes.