# US 10,503,717 B1 · Method for locating data on a deduplicated storage system using a SSD cache index > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,503,717 B1 - Document ID: US10503717B1 - Status: Granted - Kind: B1 - Application number: 14/586,184 - Filed: 2014-12-30 - Granted: 2019-12-10 - Earliest claimed: 2014-12-30 - Assignees: EMC IP Holding Company LLC - Applicants: EMC IP Holding Company LLC - Inventors: Satish Visvanathan; Mahesh Kamat; Rahul B Ugale - Web page: https://patentgrep.com/patent/US10503717B1 ## CPC - G06F 3/061: {Improving I/O performance} - G06F 16/2255: {Hash tables} - G06F 3/0608: {Saving storage space on storage systems} - G06F 3/0641: {De-duplication techniques} - G06F 3/0656: {Data buffering arrangements} - G06F 3/0679: {Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]} - G06F 3/0688: {Non-volatile semiconductor memory arrays} - G06F 16/24552: {Database cache management} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 1 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. ### Claim 2 (depends on 1) The method of claim 1, wherein the cache hash bucket only contains one byte of the fingerprint, wherein the fingerprint has two or more bytes. ### Claim 3 (depends on 1) The method of claim 1, further comprising: merging the in-memory hash table with hash table for persistent storage. ### Claim 4 (depends on 3) The method of claim 3, wherein merging the in-memory hash table with the hash table comprises inserting an entry containing a fingerprint and a container identifier into a corresponding hash bucket of the hash table. ### Claim 5 (depends on 3) The method of claim 3, wherein merging the in-memory hash table with the hash table is performed during merging of the in-memory hash table with a hard drive hash table. ### Claim 6 (depends on 5) The method of claim 5, wherein the hard drive hash table is a first of a plurality of hard drive hash tables, wherein a second of the plurality of hard drive hash tables is merging with the first of the plurality of hard drive hash tables while the in-memory hash table is merged with the first of the plurality of hard drive hash tables. ### Claim 7 (depends on 1) The method of claim 1, further comprising: mapping solid state drive buckets to hard drive buckets by configuring a solid state drive (SSD) buckets to hard drive buckets ratio. ### Claim 8 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. ### Claim 9 (depends on 8) The system of claim 8, wherein the cache hash bucket only contains one byte of the fingerprint, wherein the fingerprint has two or more bytes. ### Claim 10 (depends on 8) The system of claim 8, further comprising: merging the in-memory hash table with a hash table for persistent storage. ### Claim 11 (depends on 10) The system of claim 10, wherein merging the in-memory hash table with the hash table comprises inserting an entry containing a fingerprint and a container identifier into a corresponding hash bucket of the hash table. ### Claim 12 (depends on 10) The system of claim 10, wherein merging the in-memory hash table with the hash table is performed during merging of the in-memory hash table with a hard drive hash table. ### Claim 13 (depends on 12) The system of claim 12, wherein the hard drive hash table is a first of a plurality of hard drive hash tables, wherein a second of the plurality of hard drive hash tables is merging with the first of the plurality of hard drive hash tables while the in-memory hash table is merged with the first of the plurality of hard drive hash tables. ### Claim 14 (depends on 8) The system of claim 8, further comprising: mapping solid state drive buckets to hard drive buckets by configuring a solid state drive (SSD) buckets to hard drive buckets ratio. ### Claim 15 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. ### Claim 16 (depends on 15) The computer program product of claim 15, wherein the cache hash bucket only contains one byte of the fingerprint, wherein the fingerprint has two or more bytes. ### Claim 17 (depends on 15) The computer program product of claim 15, further comprising: merging the in-memory hash table with a hash table for persistent storage. ### Claim 18 (depends on 17) The computer program product of claim 17, wherein merging the in-memory hash table with the hash table comprises inserting an entry containing a fingerprint and a container identifier into a corresponding hash bucket of the hash table. ### Claim 19 (depends on 17) The computer program product of claim 17, wherein merging the in-memory hash table with the hash table is performed during merging of the in-memory hash table with a hard drive hash table. ### Claim 20 (depends on 19) The computer program product of claim 19, wherein the hard drive hash table is a first of a plurality of hard drive hash tables, wherein a second of the plurality of hard drive hash tables is merging with the first of the plurality of hard drive hash tables while the in-memory hash table is merged with the first of the plurality of hard drive hash tables. ### Claim 21 (depends on 15) The computer program product of claim 15, further comprising: mapping solid state drive buckets to hard drive buckets by configuring a solid state drive (SSD) buckets to hard drive buckets ratio.