Speeding de-duplication using a temporal digest cache

An apparatus for performing deduplication in a filesystem hosted on the apparatus, the apparatus comprising:

• persistent storage;
• and
• processing circuitry coupled to memory configured to:
• provide a plurality of mapping structures, each mapping structure having a set of entries associating one or more logical addresses with respective digests, each digest providing a hash value of data stored at a respective logical address, the set of entries reflecting a temporal pattern of writes;
• access a set of mapping pointers from a file pointer structure in the filesystem, each mapping pointer mapping data provided at a respective logical address of a file defined by the file pointer structure;
• follow a mapping pointer of the set of mapping pointers from the file pointer structure to a first mapping structure to identify a digest that corresponds to a logical address mapped by the mapping pointer;
• perform a lookup for the digest in a persistent digest log in the persistent storage;
• and
• in response to the digest being found in the persistent digest log:
• identify a second mapping structure that the persistent digest log associates with the digest;
• change the mapping pointer to point to the identified second mapping structure;
• access the second mapping structure;
• and
• load multiple digests that the accessed second mapping structure stores into a temporal cache within memory, the temporal cache thereby storing digests of data blocks that were previously written in a temporal pattern and being likely to again be read in a same temporal pattern, enabling the temporal cache to provide information identifying the second mapping structure as associated with other digests while avoiding accessing the persistent digest log in persistent storage in response to subsequent lookups.

A computer program product comprising a non-transitory computer-readable storage medium storing a set of instructions, which, when executed by a computing device, causes the computing device to perform deduplication in a filesystem hosted on the computing device by:

• providing a plurality of mapping structures, each mapping structure having a set of entries associating one or more logical addresses with respective digests, each digest providing a hash value of data stored at a respective logical address, the set of entries reflecting a temporal pattern of writes;
• accessing a set of mapping pointers from a file pointer structure in the filesystem, each mapping pointer mapping data provided at a respective logical address of a file defined by the file pointer structure;
• following a mapping pointer of the set of mapping pointers from the file pointer structure to a first mapping structure to identify a digest that corresponds to a logical address mapped by the mapping pointer;
• performing a lookup for the digest in a persistent digest log in persistent storage;
• and
• in response to the digest being found in the persistent digest log:
• identifying a second mapping structure that the persistent digest log associates with the digest;
• changing the mapping pointer to point to the identified second mapping structure;
• accessing the second mapping structure;
• and
• loading multiple digests that the accessed second mapping structure stores into a temporal cache within memory, the temporal cache thereby storing digests of data blocks that were previously written in a temporal pattern and being likely to again be read in a same temporal pattern, enabling the temporal cache to provide information identifying the second mapping structure as associated with other digests while avoiding accessing the persistent digest log in persistent storage in response to subsequent lookups.