Back to results
US 10,503,717 B1Granted
Method for locating data on a deduplicated storage system using a SSD cache index
AssigneeEMC IP Holding Company LLC
InventorsSatish Visvanathan, Mahesh Kamat, Rahul B Ugale
Life of this patent
Estimating the term…
Abstract
A method, article of manufacture, and apparatus for locating data inside a deduplicated storage system is discussed. An index on a solid state device may contain a finger print to container identifier mapping. The container identifier may identify a logical container storing data related to the fingerprint. This data may therefore be located using the index given the fingerprint.
Claims21
A method for locating a data segment on a deduplicated storage system, the method comprising:
- receiving, by a processing module executed by a processor of the deduplicated storage system, a fingerprint associated with the data segment for restoration of the data segment for a remote system, wherein the fingerprint is a hash of the data segment;
- applying, by the processing module, a hashing process to the fingerprint, wherein the hashing process maps the fingerprint to a hash bucket of an in-memory hash table;
- determining, by the processing module, whether the hash bucket contains the fingerprint;
- loading, by the processing module, a cache hash table from a solid state drive (“SSD”) when the bucket does not contain the fingerprint;
- applying, by the processing module, a second hashing process to the fingerprint, wherein the second hashing process maps the fingerprint to a cache hash bucket of the cache hash table, wherein the in-memory hash table merges with the cache hash table at predetermined periodic time intervals;
- determining, by the processing module, the cache hash bucket contains the finger print;
- identifying, by the processing module, a logical container identifier associated with the fingerprint in the cache hash bucket based on a scale factor and the second hashing process, wherein the cache hash bucket of the cache hash table is mapped to a hash table of the deduplicated storage system using the scale factor, wherein the scale factor is a numerical value identifying the number of hash buckets in the cache hash table of the SDD for every hash bucket of the deduplicated storage system;
- and
- returning, by the processing module, the identified logical container identifier associated with the fingerprint in the cache hash bucket for the restoration, wherein the logical container identifier uniquely identifies a logical container containing the data segment, wherein the logical container is one of a plurality of logical containers of the deduplicated storage system, wherein each of the plurality of logical containers comprises a metadata section and a data section, the metadata section being different from the data section and the metadata section contains a plurality of fingerprints each identifying one of a plurality of data segments of the data section.
6 more elements
A system for locating a data segment on a deduplicated storage system comprising a non-transitory computer readable storage medium and a processor executing instructions for:
- receiving, by a processing module executed by a processor of the deduplicated storage system, a fingerprint associated with the data segment for restoration of the data segment for a remote system, wherein the fingerprint is a hash of the data segment;
- applying, by the processing module, a hashing process to the fingerprint, wherein the hashing process maps the fingerprint to a hash bucket of an in-memory hash table;
- determining, by the processing module, whether the hash bucket contains the fingerprint;
- loading, by the processing module, a cache hash table from a solid state drive (“SSD”) when the bucket does not contain the fingerprint;
- applying, by the processing module, a second hashing process to the fingerprint, wherein the second hashing process maps the fingerprint to a cache hash bucket of the cache hash table, wherein the in-memory hash table merges with the cache hash table at predetermined periodic time intervals;
- determining, by the processing module, the cache hash bucket contains the finger print;
- identifying, by the processing module, a logical container identifier associated with the fingerprint in the cache hash bucket based on a scale factor and the second hashing process, wherein the cache hash bucket of the cache hash table is mapped to a hash table of the deduplicated storage system using the scale factor, wherein the scale factor is a numerical value identifying the number of hash buckets in the cache hash table of the SDD for every hash bucket of the deduplicated storage system;
- and
- returning, by the processing module, the identified logical container identifier associated with the fingerprint in the cache hash bucket for the restoration, wherein the logical container identifier uniquely identifies a logical container containing the data segment, wherein the logical container is one of a plurality of logical containers of the deduplicated storage system, wherein each of the plurality of logical containers comprises a metadata section and a data section, the metadata section being different from the data section and the metadata section contains a plurality of fingerprints each identifying one of a plurality of data segments of the data section.
6 more elements
A computer program product for locating a data segment on a deduplicated storage system, the computer program product comprising a non-transitory computer readable medium encoded with computer executable program, the code enabling:
- receiving, by a processing module executed by a processor of the deduplicated storage system, a fingerprint associated with the data segment for restoration of the data segment for a remote system, wherein the fingerprint is a hash of the data segment;
- applying, by the processing module, a hashing process to the fingerprint, wherein the hashing process maps the fingerprint to a hash bucket of an in-memory hash table;
- determining, by the processing module, whether the hash bucket contains the fingerprint;
- loading, by the processing module, a cache hash table from a solid state drive (“SSD”) when the bucket does not contain the fingerprint;
- applying, by the processing module, a second hashing process to the fingerprint, wherein the second hashing process maps the fingerprint to a cache hash bucket of the cache hash table, wherein the in-memory hash table merges with the cache hash table at predetermined periodic e intervals;
- determining, by the processing module, the cache hash bucket contains the finger print;
- identifying, by the processing module, a logical container identifier associated with the fingerprint in the cache hash bucket based on a scale factor and the second hashing process, wherein the cache hash bucket of the cache hash table is mapped to a hash table of the deduplicated storage system using the scale factor, wherein the scale factor is a numerical value identifying the number of hash buckets in the cache hash table of the SDD for every hash bucket of the deduplicated storage system;
- and
- returning, by the processing module, the identified logical container identifier associated with the fingerprint in the cache hash bucket for the restoration, wherein the logical container identifier uniquely identifies a logical container containing the data segment, wherein the logical container is one of a plurality of logical containers of the deduplicated storage system, wherein each of the plurality of logical containers comprises a metadata section and a data section, the metadata section being different from the data section and the metadata section contains a plurality of fingerprints each identifying one of a plurality of data segments of the data section.
6 more elements
Dependencies are inferred from the claim text.