Method and system for transferring data to a target storage system using perfect hash functions
A method for transferring data includes populating a perfect hash bit vector (PHV) using a perfect hash function (PHF) and a 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.
1. A method for transferring data, 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.
2. The method of claim 1 , wherein the populated PHV, the source index file and the target index file are stored in-memory on the target storage device.
3. The method of claim 1 , further comprising:
receiving the received segment references from the source storage device.
4. The method of claim 1 , wherein determining the required segment references using the populated PHV and the received segment references comprises:
selecting a received segment reference of the received segment references;
generating, using the PHF, a hash value for the received segment reference;
identifying a location in the populated PHV using the hash value;
making a determining that a bit value in the location is set;
based on the determination, marking the received segment reference as a required segment reference.
5. The method of claim 1 , wherein populating a perfect hash bit vector (PHV) using the perfect hash function (PHF) and the target index file to obtain the populated PHV comprises:
selecting a segment reference in the target index file;
generating, using the PHF, a hash value for the segment reference;
identifying a location in the populated PHV using the hash value;
setting a bit value in the location.
6. 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.
7. The system of claim 6 , wherein the populated PHV, the source index file and the target index file are stored in-memory on the target storage device.
8. The system of claim 6 , the method further comprising: receiving the received segment references from the source storage device.
9. The system of claim 6 , wherein determining the required segment references using the populated PHV and the received segment references comprises:
selecting a received segment reference of the received segment references;
generating, using the PHF, a hash value for the received segment reference;
identifying a location in the populated PHV using the hash value;
making a determining that a bit value in the location is set;
based on the determination, marking the received segment reference as a required segment reference.
10. 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.
11. The non-transitory computer readable medium of claim 10 , wherein the populated PHV, the source index file and the target index file are stored in-memory on the target storage device.
12. The non-transitory computer readable medium of claim 10 , the method further comprising:
receiving the received segment references from the source storage device.
13. The non-transitory computer readable medium of claim 10 , wherein determining required segment references using the populated PHV and received segment references comprises:
selecting a received segment reference of the received segment references;
generating, using the PHF, a hash value for the received segment reference;
identifying a location in the populated PHV using the hash value;
making a determining that a bit value in the location is set;
based on the determination, marking the received segment reference as a required segment reference.
14. The non-transitory computer readable medium of claim 10 , wherein populating a perfect hash bit vector (PHV) using the perfect hash function (PHF) and the target index file to obtain the populated PHV comprises:
selecting a segment reference in the target index file;
generating, using the PHF, a hash value for the segment reference;
identifying a location in the populated PHV using the hash value;
setting a bit value in the location.