Method or an apparatus for having perfect deduplication, adapted for saving space in a deduplication file system
A data management device includes a persistent storage and a processor. The persistent storage includes an object storage. The processor generates a collision free hash function based on segments stored in the object storage. The processor generates a hash vector using the collision free hash function. The processor deduplicates the segments using the hash vector. The processor stores the deduplicated segments in the object storage.
1. A data management device, comprising:
a persistent storage comprising an object storage; and
a processor programmed to perform a method, comprising:
making a first determination that segments stored in the object storage are cold;
generating, based on the first determination, a hash function based on the segments;
generating a hash vector using the hash function, wherein the hash vector is a perfect hash live vector comprising a number of bits corresponding to a number of unique segments stored in the object storage;
deduplicating the segments using the hash vector, wherein deduplicating the segment comprises:
matching each fingerprint of each segment to a plurality of bits of the hash vector;
making a second determination that a plurality of fingerprints match a first bit of the plurality of bits;
identifying, based on the second determination, a first segment associated with a first fingerprint of the plurality of fingerprints;
marking the first segment as unique; and
deleting all of the segments associated with the plurality of fingerprints other than the first segment; and
storing the deduplicated segments in the object storage.
2. The data management device of claim 1 , wherein the hash function is a perfect hash function.
3. The data management device of claim 2 , wherein the hash function maps each unique segment in the object storage to a different bit in the hash vector.
4. The data management device of claim 1 , wherein deduplicating the segments using the hash vector further comprises:
identifying a file recipe that specifies a segment of the deleted segments associated with the plurality of fingerprints other than the first segment; and
updating the identified file recipe based on the first segment associated with the first fingerprint of the plurality of fingerprints.
5. The data management device of claim 1 , wherein storing the deduplicated segments in the object storage comprises:
packing the deduplicated segments into an object of the object storage; and
super compressing the packed segments.
6. The data management device of claim 1 , wherein the method further comprises:
obtaining a data access request that requests a first file stored in the object storage;
obtaining a first file recipe associated with the first file;
generating the first file, based on the first file recipe, using the first segment stored in the object storage and a second segment stored in the object storage, wherein the first segment is also associated with a second file; and
providing the first file in response to the data access request.
7. A method of operating a data management device, comprising:
making a first determination, by the data management device, that segments stored in an object storage are cold;
generating, based on the first determination, a hash function based on the segments;
generating a hash vector using the hash function, wherein the hash vector is a perfect hash live vector comprising a number of bits corresponding to a number of unique segments stored in the object storage;
deduplicating the segments using the hash vector, wherein deduplicating the segment comprises:
matching each fingerprint of each segment to a plurality of bits of the hash vector:
making a second determination that a plurality of fingerprints match a first bit of the plurality of bits;
identifying, based on the second determination, a first segment associated with a first fingerprint of the plurality of fingerprints;
marking the first segment as unique; and
deleting all of the segments associated with the plurality of fingerprints other than the first segment; and
storing the deduplicated segments in the object storage.
8. The method of claim 7 , wherein deduplicating the segments using the hash vector further comprises:
identifying a file recipe that specifies a segment of the deleted segments associated with the plurality of fingerprints other than the first segment; and
updating the identified file recipe based on the first segment associated with the first fingerprint of the plurality of fingerprints.
9. The method of claim 7 , wherein the method further comprises:
obtaining a data access request that requests a first file stored in the object storage;
obtaining a first file recipe associated with the first file;
generating the first file, based on the first file recipe, using the first segment stored in the object storage and a second segment stored in the object storage, wherein the first segment is also associated with a second file; and
providing the first file in response to the data access request.
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 for operating a data management device, the method comprising:
making a first determination, by the data management device, that segments stored in an object storage are cold;
generating, based on the first determination, a hash function based on the segments;
generating a hash vector using the hash function, wherein the hash vector is a perfect hash live vector comprising a number of bits corresponding to a number of unique segments stored in the object storage;
deduplicating the segments using the hash vector, wherein deduplicating the segment comprises:
matching each fingerprint of each segment to a plurality of bits of the hash vector;
making a second determination that a plurality of fingerprints match a first bit of the plurality of bits;
identifying, based on the second determination, a first segment associated with a first fingerprint of the plurality of fingerprints;
marking the first segment as unique; and
deleting all of the segments associated with the plurality of fingerprints other than the first segment; and
storing the deduplicated segments in the object storage.
11. The non-transitory computer readable medium of claim 10 , wherein the method further comprises:
obtaining a data access request that requests a first file stored in the object storage;
obtaining a first file recipe associated with the first file;
generating the first file, based on the first file recipe, using the first segment stored in the object storage and a second segment stored in the object storage, wherein the first segment is also associated with a second file; and
providing the first file in response to the data access request.