Granted Patent B2

US 9,501,545 · App. 13/920,923 · Granted Nov 22, 2016

Abstract

Claims (85)

1. A computerized method for caching hashes for requested deduplicated data such that hashes associated with data related to the requested deduplicated data is pre-loaded, thereby improving a reading speed of the related data, the computerized method comprising:

receiving, by a computing device, a request to read requested data from a deduplication data store;

identifying, by the computing device, in a first hash structure that is not stored in memory of the computing device, a persist header stored in the deduplication data store, wherein:

the persist header comprises a set of hashes that includes a hash that is indicative of the requested data; and

each hash in the set of hashes represents a portion of data stored in the deduplication data store, wherein the requested data is co-located with other portions of data, the requested data and the other portions of data appended to the set of hashes, further wherein the other portions of data are represented by the remaining hashes in the set of hashes; and

caching, by the computing device, the set of hashes in a second hash structure stored in the memory of the computing device, whereby if the computing device requests to read additional data, the computing device can identify the additional data using the second hash structure if the additional data is represented by the persist header, thereby enabling the caching of hashes for requested deduplicated data such that hashes associated with data related to the requested deduplicated data is pre-loaded, thereby improving a reading speed of the related data.

2. The method of claim 1 , wherein caching the set of hashes in the second hash structure stored in the memory of the computing device comprises:

storing a hash table structure in a hash table array based on the persist header, the hash table structure comprising:

a hash fragment comprising a portion of the hash of the data;

an index into a persist header reference array; and

a hash index into the set of hashes for the persist header that identifies the hash for the data.

3. The method of claim 2 , further comprising:

identifying the hash table structure in the hash table array based on the hash fragment.

4. The method of claim 2 , further comprising:

storing a persist header reference structure in a persist header reference array based on the persist header, the persist header reference structure comprising:

a cache page index into a cache page array that identifies the persist header in memory; and

a hash code to verify an identity of a cache page array entry identified by the cache page index.

5. The method of claim 4 , further comprising reading data associated with the persist header, comprising:

identifying the hash table structure in the hash table array based on the hash fragment; and

identifying the persist header reference structure in the persist header reference array based on the index.

6. The method of claim 5 , further comprising:

identifying the cache page array entry in the cache page index based on the cache page index; and

verifying an identity of the cache page array entry based on the hash code.

7. The method of claim 6 , further comprising:

identifying the persist header in memory based on the cache page array; and

identifying the hash in the set of hashes based on the index.

8. The method of claim 1 , further comprising:

receiving a second request to read second data from the deduplication data store; and

identifying the second data using the second hash structure and not the first hash structure, wherein the second data comprises a second hash in the set of hashes.

9. The method of claim 1 , comprising:

receiving a second request to read second data from the deduplication data store;

determining a second hash for the second data is not in the second hash structure;

identifying a second persist header in the first hash structure, wherein:

the second persist header comprises a second hash in a second set of hashes stored in the second persist header; and

the second hash is indicative of the second data the computing device requested to read; and

caching the second set of hashes in the second hash structure stored in the memory of the computing device.

10. A computing device for caching hashes for requested deduplicated data such that hashes associated with data related to the requested deduplicated data is pre-loaded, thereby improving a reading speed of the related data, the computing device comprising:

a deduplication data store; and

a processor in communication with the deduplication data store, and configured to run a module stored in memory that is configured to cause the processor to:

receive a request to read requested data from the deduplication data store;

identify in a first hash structure that is not stored in the memory of the computing device, a persist header stored in the deduplication data store, wherein:

the persist header comprises a set of hashes that includes a hash that is indicative of the requested data; and

each hash in the set of hashes represents a portion of data stored in the deduplication data store, wherein the requested data is co-located with other portions of data, the requested data and the other portions of data appended to the set of hashes, further wherein the other portions of data are represented by the remaining hashes in the set of hashes; and

cache the set of hashes in a second hash structure stored in the memory of the computing device, whereby if the computing device requests to read additional data, the computing device can identify the additional data using the second hash structure if the additional data is represented by the persist header, thereby enabling the caching of hashes for requested deduplicated data such that hashes associated with data related to the requested deduplicated data is pre-loaded, thereby improving a reading speed of the related data.

11. A non-transitory computer readable medium having executable instructions operable to cause an apparatus to:

receive a request to read requested data from a deduplication data store;

identify in a first hash structure that is not stored in memory of the apparatus, a persist header stored in the deduplication data store, wherein:

the persist header comprises a set of hashes that includes a hash that is indicative of the requested data; and

each hash in the set of hashes represents a portion of data stored in the deduplication data store, wherein the requested data is co-located with other portions of data, the requested data and the other portions of data appended to the set of hashes, further wherein the other portions of data are represented by the remaining hashes in the set of hashes; and

cache the set of hashes in a second hash structure stored in the memory of the apparatus, whereby if the apparatus requests to read additional data, the apparatus can identify the additional data using the second hash structure if the additional data is represented by the persist header, thereby enabling the caching of hashes for requested deduplicated data such that hashes associated with data related to the requested deduplicated data is pre-loaded, thereby improving a reading speed of the related data.

12. The computing device of claim 10 , wherein caching the set of hashes in the second hash structure stored in the memory of the computing device comprises:

storing a hash table structure in a hash table array based on the persist header, the hash table structure comprising:

a hash fragment comprising a portion of the hash of the data;

an index into a persist header reference array; and

a hash index into the set of hashes for the persist header that identifies the hash for the data.

13. The computing device of claim 12 , wherein the processor is further configured to:

identify the hash table structure in the hash table array based on the hash fragment.

14. The computing device of claim 12 , wherein the processor is further configured to:

store a persist header reference structure in a persist header reference array based on the persist header, the persist header reference structure comprising:

a cache page index into a cache page array that identifies the persist header in memory; and

a hash code to verify an identity of a cache page array entry identified by the cache page index.

15. The computing device of claim 14 , wherein the processor is further configured to read data associated with the persist header, wherein reading data associated with the persist header comprises:

identifying the hash table structure in the hash table array based on the hash fragment; and

identifying the persist header reference structure in the persist header reference array based on the index.

16. The computing device of claim 15 , wherein the processor is further configured to:

identify the cache page array entry in the cache page index based on the cache page index; and

verify an identity of the cache page array entry based on the hash code.

17. The computing device of claim 16 , wherein the processor is further configured to:

identify the persist header in memory based on the cache page array; and

identify the hash in the set of hashes based on the index.

18. The computing device of claim 10 , wherein the processor is further configured to:

receive a second request to read second data from the deduplication data store; and

identify the second data using the second hash structure and not the first hash structure, wherein the second data comprises a second hash in the set of hashes.

19. The computing device of claim 10 , wherein the processor is further configured to:

receive a second request to read second data from the deduplication data store;

determine a second hash for the second data is not in the second hash structure;

identify a second persist header in the first hash structure, wherein:

the second persist header comprises a second hash in a second set of hashes stored in the second persist header; and

the second hash is indicative of the second data the computing device requested to read; and

caching the second set of hashes in the second hash structure stored in the memory of the computing device.

20. The non-transitory computer readable medium of claim 11 , wherein caching the set of hashes in the second hash structure stored in the memory of the apparatus comprises:

storing a hash table structure in a hash table array based on the persist header, the hash table structure comprising:

a hash fragment comprising a portion of the hash of the data;

an index into a persist header reference array; and

a hash index into the set of hashes for the persist header that identifies the hash for the data.

Assignments (8)