Memory efficient sanitization of a deduplicated storage system using a perfect hash function

A non-transitory computer-readable medium having instructions stored therein, which when executed by a computer, cause the computer to perform operations, the operations comprising:

• for each of fingerprints representing data chunks stored in a first of a plurality of containers of the storage system,
• identifying a bucket associated with the fingerprint by applying a first hash function to the fingerprint, wherein the bucket represents a subset of fingerprints;
• determining a second hash function corresponding to the identified bucket, the second hash function is a collision free hash function;
• applying the second hash function to the fingerprint to generate a hash value;
• performing a lookup operation in a single live bit vector using the hash value as an index to determine a live status of a corresponding data chunk, the single live bit vector having a plurality of bits and each indicating whether one of a plurality of data chunks stored in the plurality of containers is live or dead, and
• populating a bit in a copy bit vector (CBV) corresponding to the data chunk based on the lookup operation by copying the determined live status from the single live bit vector to the bit in the CBV, the CBV including a plurality of bits and each storing a bit value indicating whether a data chunk is to be copied, wherein each bit in the CBV is referenced by a container ID and a data chunk ID associated with the fingerprint;
• after all of the bits corresponding to the data chunks of the first container have been populated in the CBV, copying live data chunks represented by the CBV from the first container to a second container;
• erasing records of the data chunks by padding a predetermined data value in the first container;
• and
• releasing the first container back to a pool of free containers for future reuse.

A data processing system, comprising:

• a processor;
• and
• a memory to store instructions, which when executed from the memory, cause the
• processor to
• for each of fingerprints representing data chunks stored in a first of a plurality of containers of the storage system,
• identify a bucket associated with the fingerprint by applying a first hash function to the fingerprint, wherein the bucket represents a subset of fingerprints;
• determine a second hash function corresponding to the identified bucket, the second hash function is a collision free hash function,
• apply the second hash function to the fingerprint to generate a hash value,
• perform a lookup operation in a single live bit vector using the hash value as an index to determine a live status of a corresponding data chunk, the single live bit vector having a plurality of bits and each indicating whether one of a plurality of data chunks stored in the plurality of containers is live or dead, and
• populate a bit in a copy bit vector (CBV) corresponding to the data chunk based on the lookup operation by copying the determined live status from the single live bit vector to the bit in the CBV, the CBV including a plurality of bits and each storing a bit value indicating whether a data chunk is to be copied, wherein each bit in the CBV is referenced by a container ID and a data chunk ID associated with the fingerprint;
• after all of the bits corresponding to the data chunks of the first container have been populated in the CBV, copy live data chunks represented by the CBV from the first container to a second container;
• erase records of the data chunks by padding a predetermined data value in the first container;
• and
• release the first container back to a pool of free containers for future reuse.