Back to results
US 9,286,314 B2Granted
Applying a maximum size bound on content defined segmentation of data
AssigneeInternational Business Machines Corporation
InventorLior Aronovich
Life of this patent
Estimating the term…
Abstract
Applying a content defined maximum size bound on blocks produced by content defined segmentation of data by calculating the size of the interval of data between a newly found candidate segmenting position and a last candidate segmenting position of the same or higher hierarchy level, and then using the intermediate candidate segmenting positions of that interval if the size of the interval exceeds the maximum size bound, or discarding the intermediate candidate segmenting positions of that interval if the size of the interval does not exceed the maximum size bound.
Claims22
A method for applying a content defined maximum size bound on content defined segmentation of data into blocks using a processor device in a computing environment, comprising:
- defining a plurality of segmenting probabilities and a plurality of segmenting conditions, wherein each of the plurality of segmenting conditions is associated with one of the plurality of segmenting probabilities;
- ordering the plurality of segmenting conditions in accordance with the associated one of the plurality of segmenting probabilities to form a hierarchy of the plurality of segmenting conditions;
- defining a segmenting condition associated with a highest segmenting probability to be a lowest level segmenting condition in the hierarchy of the plurality of segmenting conditions, and defining the segmenting condition associated with a lowest segmenting probability to be a highest level segmenting condition in the hierarchy of the plurality of segmenting conditions;
- defining a maximum bound on a size of a block;
- calculating a plurality of hash values for each seed block in each consecutive byte position in the data;
- evaluating each one of the plurality of hash values using the plurality of segmenting conditions;
- determining a position of one of the plurality of hash values as a candidate segmenting position in the data if at least one of the plurality of segmenting conditions is satisfied by the hash value;
- defining a hierarchy level of a candidate segmenting position as the hierarchy level of the highest level segmenting condition that is satisfied by the one of the plurality of hash values of the candidate segmenting position;
- recording candidate segmenting positions with hierarchy levels of the candidate segmenting positions;
- calculating the size of the interval of data between a newly found candidate segmenting position and a previous candidate segmenting position;
- and
- determining the candidate segmenting positions of the interval of data to be actual segmenting positions if the size of the interval of data exceeds the maximum bound on the size of the block.
9 more elements
A system for applying a content defined maximum size bound on content defined blocks of a computing environment, the system comprising:
- a repository operating in the computing environment;
- a memory in association with the repository;
- and
- at least one processor device operable in the computing storage environment for controlling the data deduplication system and in communication with the repository and the memory, wherein the at least one processor device:
- defines a plurality of segmenting probabilities and a plurality of segmenting conditions, wherein each of the plurality of segmenting conditions is associated with one of the plurality of segmenting probabilities,
- orders the plurality of segmenting conditions in accordance with the associated one of the plurality of segmenting probabilities to form a hierarchy of the plurality of segmenting conditions,
- defines a segmenting condition associated with a highest segmenting probability to be a lowest level segmenting condition in the hierarchy of the plurality of segmenting conditions, and defining the segmenting condition associated with a lowest segmenting probability to be a highest level segmenting condition in the hierarchy of the plurality of segmenting conditions,
- defines a maximum bound on a size of a block,
- calculates a plurality of hash values for each seed block in each consecutive byte position in data,
- evaluates each one of the plurality of hash values using the plurality of segmenting conditions,
- determines a position of one of the plurality of hash values as a candidate segmenting position in the data if at least one of the plurality of segmenting conditions is satisfied by the hash value,
- defines a hierarchy level of a candidate segmenting position as the hierarchy level of the highest level segmenting condition that is satisfied by the one of the plurality of hash values of the candidate segmenting position,
- records candidate segmenting positions with hierarchy levels of the candidate segmenting positions,
- calculates the size of the interval of data between a newly found candidate segmenting position and a previous candidate segmenting position, and
- determines the candidate segmenting positions of the interval of data to be actual segmenting positions if the size of the interval of data exceeds the maximum bound on the size of the block.
12 more elements
A computer program product for applying a content defined maximum size bound on content defined blocks using a processor device in a computing environment, the computer program product comprising a computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions comprising:
- a first executable portion that defines a plurality of segmenting probabilities and a plurality of segmenting conditions, wherein each of the plurality of segmenting conditions is associated with one of the plurality of segmenting probabilities;
- a second executable portion that orders the plurality of segmenting conditions in accordance with the associated one of the plurality of segmenting probabilities to form a hierarchy of the plurality of segmenting conditions;
- a third executable portion that defines a segmenting condition associated with a highest segmenting probability to be a lowest level segmenting condition in the hierarchy of the plurality of segmenting conditions, and defining the segmenting condition associated with a lowest segmenting probability to be a highest level segmenting condition in the hierarchy of the plurality of segmenting conditions;
- a fourth executable portion that defines a maximum bound on a size of a block;
- a fifth executable portion that calculates a plurality of hash values for each seed block in each consecutive byte position in data;
- a sixth executable portion that evaluates each one of the plurality of hash values using the plurality of segmenting conditions;
- a seventh executable portion that determines a position of one of the plurality of hash values as a candidate segmenting position in the data if at least one of the plurality of segmenting conditions is satisfied by the hash value;
- an eighth executable portion that defines a hierarchy level of a candidate segmenting position as the hierarchy level of the highest level segmenting condition that is satisfied by the one of the plurality of hash values of the candidate segmenting position;
- a ninth executable portion that records candidate segmenting positions with hierarchy levels of the candidate segmenting positions;
- a tenth executable portion that calculates the size of the interval of data between a newly found candidate segmenting position and a previous candidate segmenting position;
- and
- an eleventh executable portion that determines the candidate segmenting positions of the interval of data to be actual segmenting positions if the size of the interval of data exceeds the maximum bound on the size of the block.
9 more elements
Dependencies are inferred from the claim text.