Locality aware, two-level fingerprint caching
The present disclosure provides for implementing a two-level fingerprint caching scheme for a client cache and a server cache. The client cache hit ratio can be improved by pre-populating the client cache with fingerprints that are relevant to the client. Relevant fingerprints include fingerprints used during a recent time period (e.g., fingerprints of segments that are included in the last full backup image and any following incremental backup images created for the client after the last full backup image), and thus are referred to as fingerprints with good temporal locality. Relevant fingerprints also include fingerprints associated with a storage container that has good spatial locality, and thus are referred to as fingerprints with good spatial locality. A pre-set threshold established for the client cache (e.g., threshold Tc) is used to determine whether a storage container (and thus fingerprints associated with the storage container) has good spatial locality.
1. A method comprising:
pre-populating a cache of a client (“client cache”) with relevant fingerprints received from a server, wherein
each of the relevant fingerprints corresponds to a data segment in a deduplicated data store on the server, and
the pre-populating is performed in response to initiation of a backup process of the client,
the pre-populating comprises
retrieving the relevant fingerprints from the server based on, at least in part, a client name,
storing the relevant fingerprints in a buffer list in the client cache, and
sorting the relevant fingerprints in the buffer list based on a container ID value;
determining whether one or more generated fingerprints are present in the client cache during a deduplication process, subsequent to the pre-populating, wherein
the generated fingerprints are generated from client data during the backup process, and
the deduplication process is part of the backup process; and
in response to determining that at least one generated fingerprint of the one or more generated fingerprints is present in the client cache, transmitting the at least one generated fingerprint to the server, wherein
each of the at least one generated fingerprints comprises information configured to be used during the deduplication process.
2. The method of claim 1 , further comprising:
determining whether the one or more generated fingerprints are present in a server cache, in response to a client cache miss.
3. The method of claim 2 , further comprising:
recording metadata about whether the one or more generated fingerprints are present in the client cache and the server cache; and
sending the metadata to the server, wherein
the metadata is used to update a central index of fingerprints stored in the server cache.
4. The method of claim 1 , wherein
the relevant fingerprints identify data segments included in one or more previous backup images of the client.
5. The method of claim 1 , wherein the pre-populating further comprises:
identifying one or more groups of fingerprints in the sorted fingerprints, wherein
each of the one or more groups of fingerprints comprises one or more fingerprints that are associated with a same container ID.
6. The method of claim 1 , wherein the pre-populating further comprises:
determining whether a storage container associated with a group of relevant fingerprints has good spatial locality, wherein
the group is associated with a same container ID that identifies the storage container.
7. The method of claim 6 , wherein the determining whether the storage container has good spatial locality further comprises:
determining whether the storage container is associated with at least a threshold number of fingerprints.
8. The method of claim 6 , wherein the determining whether the storage container has good spatial locality further comprises:
determining whether the storage container includes at least a threshold amount of data.
9. The method of claim 6 , wherein the pre-populating further comprises:
adding the group of relevant fingerprints to the client cache, in response to a determination that the storage container has good spatial locality.
10. A system comprising:
a server; and
a client, communicatively coupled to the server, comprising:
a cache of a client (“client cache”), and
a client cache processing module configured to
pre-populate the client cache with relevant fingerprints received from the server, in response to initiation of a backup process of the client, wherein,
each of the relevant fingerprints corresponds to a data segment in a deduplicated data store on the server,
the client cache is pre-populated by retrieving the relevant fingerprints from the server based on, at least in part, a client name,
store the relevant fingerprints in a buffer list in the client cache,
sort the relevant fingerprints in the buffer list based on a container ID value,
determine whether one or more generated fingerprints are present in the client cache during a deduplication process, subsequent to pre-population of the client cache; and
in response to a determination that at least one generated fingerprint of the one or more generated fingerprints is present in the client cache, transmit the at least one generated fingerprint to the server, wherein
each of the at least one generated fingerprints comprises information configured to be used during the deduplication process.
11. The system of claim 10 , wherein the server further comprises:
a server cache, and
a server cache processing module configured to
determine whether the one or more generated fingerprints are present in the server cache, in response to a request from the client cache processing module.
12. The system of claim 11 , wherein the client cache processing module is further configured to
record metadata about whether the one or more generated fingerprints are present in the client cache and the server cache; and
send the metadata to the server, wherein
the metadata is used to update a central index of fingerprints stored in the server cache.
13. The system of claim 10 , wherein
the relevant fingerprints identify data segments included in one or more previous backup images of the client.
14. The system of claim 10 , wherein the client cache processing module is further configured to
identify one or more groups of fingerprints in the sorted fingerprints, wherein
each of the one or more groups of fingerprints comprises one or more fingerprints that are associated with a same container ID.
15. The system of claim 10 , wherein the client cache processing module is further configured to
determine whether a storage container associated with a group of relevant fingerprints has good spatial locality, wherein
the group is associated with a container ID that identifies the storage container.
16. The system of claim 15 , wherein the client cache processing module is further configured to
determine whether the storage container is associated with at least a threshold number of fingerprints.
17. The system of claim 15 , wherein the client cache processing module is further configured to
determine whether the storage container includes at least a threshold amount of data.
18. The system of claim 15 , wherein the client cache processing module is further configured to
add the group of relevant fingerprints to the client cache, in response to a determination that the storage container has good spatial locality.
19. A non-transitory computer readable storage medium configured to store program instructions that, when executed on a processor, are configured to cause the processor to perform a method comprising:
pre-populating a cache of a client (“client cache”) with relevant fingerprints received from a server, wherein
each of the relevant fingerprints corresponds to a data segment in a deduplicated data store on the server,
the pre-populating is performed in response to initiation of a backup process of the client,
the pre-populating comprises
retrieving the relevant fingerprints from the server based on, at least in part, a client name,
storing the relevant fingerprints in a buffer list in the client cache, and
sorting the relevant fingerprints in the buffer list based on a container ID value;
determining whether one or more generated fingerprints are present in the client cache during a deduplication process, subsequent to the pre-populating, wherein
the generated fingerprints are generated from client data during the backup process, and
the deduplication process is part of the backup process; and
in response to determining that at least one generated fingerprint of the one or more generated fingerprints is present in the client cache, transmitting the at least one generated fingerprint to the server, wherein
each of the at least one generated fingerprints comprises information configured to be used during the deduplication process.
20. The non-transitory computer readable storage medium of claim 19 , wherein the method further comprises:
determining whether a storage container associated with a group of relevant fingerprints has good spatial locality, wherein
the group of relevant fingerprints comprises one or more fingerprints, and
the one or more fingerprints are associated with a same container ID that identifies the storage container.