Method and system for building content for a de-duplication engine
Disclosed herein are systems and method for building content for a de-duplication engine. In one aspect, an exemplary method comprises periodically receiving instructions for cycling through a coalescing phase and a sedimentation phase of the de-duplication engine, during a first coalescing phase, selecting a set of seed blocks that are similar to each other, when an instruction for proceeding to a next sedimentation phase is received, entering the sedimentation phase during which newly received blocks are processed to be stored near similar seed blocks, and when an instruction to proceed to a next coalescing phase is received, entering the coalescing phase to update the set of seed blocks.
1. A method for building content for a de-duplication engine, the method comprising:
periodically receiving instructions for cycling through a coalescing phase and a sedimentation phase of the de-duplication engine;
during the coalescing phase:
identifying a plurality of blocks at the de-duplication engine;
updating a set of seed blocks from the plurality of blocks by:
creating a counting hash set for storing every hash component of every block in the plurality of blocks that is not de-duplicated;
defining a counting set for hash components, wherein an element count in the counting set is used for keeping track of a number of blocks comprising a given hash component;
iteratively, for all the blocks that are not de-duplicated, looking up element counts for each hash component of the block; and
for each respective block, determining that the respective block is a seed block when at least a predetermined number of the hash components of the respective block have a respective element count that reaches a predetermined threshold, wherein the predetermined number is based on a length of time since the set of seed blocks has been updated;
when an instruction for proceeding to the sedimentation phase is received, entering the sedimentation phase comprising:
receiving at least one new block at the de-duplication engine;
identifying a portion of the at least one new block that does not match any portions of the set of seed blocks; and
storing the portion of the at least one new block at the de-duplication engine; and
when an instruction to proceed to a next coalescing phase is received, entering the next coalescing phase to update the set of seed blocks.
2. The method of claim 1 , wherein the predetermined number is further set based on a performance measurement of the set of seed blocks.
3. The method of claim 2 , wherein the performance measurement is made for determination of a need to expand the set of seed blocks, the measurement being based on an amount of matching hash components between of a sample of newly received blocks and a current set of seed blocks.
4. The method of claim 1 , wherein instructions for cycling through the coalescing phase and the sedimentation phase of the de-duplication engine are received from a monitor of the de-duplication engine.
5. The method of claim 4 , wherein the monitor of the de-duplication engine iterates a sequence number whenever an operating phase switches between a given coalescing phase and a given sedimentation phase.
6. The method of claim 1 , wherein the cycling further includes a cleaning phase in which data and objects no longer needed are removed from the de-duplication engine.
7. A system for building content for a de-duplication engine, comprising:
at least one processor of a server, the processor configured to:
periodically receive instructions for cycling through a coalescing phase and a sedimentation phase of the de-duplication engine;
during the coalescing phase:
identify a plurality of blocks at the de-duplication engine;
update a set of seed blocks from the plurality of blocks by:
create a counting hash set for storing every hash component of every block in the plurality of blocks that is not de-duplicated;
define a counting set for hash components, wherein an element count in the counting set is used for keeping track of a number of blocks comprising a given hash component;
iteratively, for all the blocks that are not de-duplicated, look up element counts for each hash component of the block; and
for each respective block, determine that the respective block is a seed block when at least a predetermined number of the hash components of the respective block have a respective element count that reaches a predetermined threshold, wherein the predetermined number is based on a length of time since the set of seed blocks has been updated;
when an instruction for proceeding to the sedimentation phase is received, enter the sedimentation phase comprising:
receiving at least one new block at the de-duplication engine;
identifying a portion of the at least one new block that does not match any portions of the set of seed blocks; and
storing the portion of the at least one new block at the de-duplication engine; and
when an instruction to proceed to a next coalescing phase is received, enter the next coalescing phase to update the set of seed blocks.
8. The system of claim 7 , wherein the predetermined number is further set based on a performance measurement of the set of seed blocks.
9. The system of claim 8 , wherein the performance measurement is made for determination of a need to expand the set of seed blocks, the measurement being based on an amount of matching hash components between of a sample of newly received blocks and a current set of seed blocks.
10. The system of claim 7 , wherein instructions for cycling through the coalescing phase and the sedimentation phase of the de-duplication engine are received from a monitor of the de-duplication engine.
11. The system of claim 10 , wherein the monitor of the de-duplication engine iterates a sequence number whenever an operating phase switches between a given coalescing phase and a given sedimentation phase.
12. The system of claim 7 , wherein the cycling further includes a cleaning phase in which data and objects no longer needed are removed from the de-duplication engine.
13. A non-transitory computer readable medium storing thereon computer executable instructions for building content for a de-duplication engine, including instructions for:
periodically receiving instructions for cycling through a coalescing phase and a sedimentation phase of the de-duplication engine;
during the coalescing phase:
identifying a plurality of blocks at the de-duplication engine;
updating a set of seed blocks from the plurality of blocks by:
creating a counting hash set for storing every hash component of every block in the plurality of blocks that is not de-duplicated;
defining a counting set for hash components, wherein an element count in the counting set is used for keeping track of a number of blocks comprising a given hash component;
iteratively, for all the blocks that are not de-duplicated, looking up element counts for each hash component of the block; and
for each respective block, determining that the respective block is a seed block when at least a predetermined number of the hash components of the respective block have a respective element count that reaches a predetermined threshold, wherein the predetermined number is based on a length of time since the set of seed blocks has been updated;
when an instruction for proceeding to the sedimentation phase is received, entering the sedimentation phase comprising:
receiving at least one new block at the de-duplication engine;
identifying a portion of the at least one new block that does not match any portions of the set of seed blocks; and
storing the portion of the at least one new block at the de-duplication engine; and
when an instruction to proceed to a next coalescing phase is received, entering the next coalescing phase to update the set of seed blocks.
14. The non-transitory computer readable medium of claim 13 , wherein the predetermined number is further set based on a performance measurement of the set of seed blocks.
15. The non-transitory computer readable medium of claim 14 , wherein the performance measurement is made for determination of a need to expand the set of seed blocks, the measurement being based on an amount of matching hash components between of a sample of newly received blocks and a current set of seed blocks.
16. The non-transitory computer readable medium of claim 13 , wherein instructions for cycling through the coalescing phase and the sedimentation phase of the de-duplication engine are received from a monitor of the de-duplication engine.
17. The non-transitory computer readable medium of claim 16 , wherein the monitor of the de-duplication engine iterates a sequence number whenever an operating phase switches between a given coalescing phase and a given sedimentation phase.
18. The non-transitory computer readable medium of claim 13 , wherein the cycling further includes a cleaning phase in which data and objects no longer needed are removed from the de-duplication engine.