Method and system for transferring data to a target storage system using perfect hash functions

A system, comprising:

• a processor;
• memory comprising a populated perfect hash bit vector (PHV) and instructions, which when executed by the processor perform a method, the method comprising:
• receiving a source index file from a source storage device,
• wherein the source index file comprises a first plurality of segment references, and
• wherein each of the first plurality of segment references corresponds to a segment stored on the source storage device;
• generating a perfect hash function (PHF) using the source index file and a target index file,
• wherein the target index file comprises a second plurality of segment references,
• wherein each of the second plurality of segment references corresponds to a segment stored on a target storage device, and
• wherein the generating the PHF comprises obtaining a union of the first plurality of segment references and the second plurality of segment references;
• populating a perfect hash bit vector (PHV) using the PHF and the target index file to obtain a populated PHV;
• determining required segment references using the populated PHV and received segment references;
• providing the required segment references to a source storage device;
• and
• receiving segments corresponding to the required segment references from the source storage device.

A non-transitory computer readable medium comprising computer readable program code, which when executed by a computer processor enables the computer processor to perform a method, the method comprising:

• receiving a source index file from a source storage device,
• wherein the source index file comprises a first plurality of segment references, and
• wherein each of the first plurality of segment references corresponds to a segment stored on the source storage device;
• generating a perfect hash function (PHF) using the source index file and a target index file,
• wherein the target index file comprises a second plurality of segment references,
• wherein each of the second plurality of segment references corresponds to a segment stored on a target storage device, and
• wherein the generating the PHF comprises obtaining a union of the first plurality of segment references and the second plurality of segment references;
• populating a perfect hash bit vector (PHV) using the PHF and the target index file to obtain a populated PHV;
• determining required segment references using the populated PHV and received segment references;
• providing the required segment references to a source storage device;
• and
• receiving segments corresponding to the required segment references from the source storage device.