# US 10,481,835 B2 · Methods and systems for dynamic hashing in caching sub-systems > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,481,835 B2 - Document ID: US10481835B2 - Status: Granted - Kind: B2 - Application number: 14/510,829 - Filed: 2014-10-09 - Published: 2016-04-14 - Granted: 2019-11-19 - Earliest claimed: 2014-10-09 - Assignees: NetApp, Inc. - Applicants: Netapp, Inc. - Inventors: Arindam Banerjee; Donald R. Humlicek - Web page: https://patentgrep.com/patent/US10481835B2 ## CPC - G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]} - G06F 3/0611: {in relation to response time} - G06F 3/0638: {Organizing or formatting or addressing of data} - G06F 12/0868: Data transfer between cache memory and other subsystems, e.g. storage devices or host systems - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Methods and systems for dynamic hashing in cache sub-systems are provided. The method includes analyzing a plurality of input/output (I/O) requests for determining a pattern indicating if the I/O requests are random or sequential; and using the pattern for dynamically changing a first input to a second input for computing a hash index value by a hashing function that is used to index into a hashing data structure to look up a cache block to cache an I/O request to read or write data, where for random I/O requests, a segment size is the first input to a hashing function to compute a first hash index value and for sequential I/O requests, a stripe size is used as the second input for computing a second hash index value. ## Claims ### Claim 1 A machine implemented method, comprising: analyzing a plurality of input/output (I/O) requests to determine a pattern indicating if the I/O requests are random or sequential; and using the pattern for dynamically changing a first input to a second input for computing a hash index value by a hashing function that is used to index into a hashing data structure to look up a cache block to cache an I/O request to read or write data; wherein for random I/O requests, a segment size is the first input to a hashing function to compute a first hash index value and for sequential I/O requests, a stripe size is used as the second input for computing a second hash index value. ### Claim 2 (depends on 1) The method of claim 1, further comprising: reconfiguring a set of cache blocks when input to the hashing function changes from the first input to the second input; wherein one or more of the set of cache blocks remain accessible using the first hash index value and one or more of the set of cache blocks is accessible using the second hash index value. ### Claim 3 (depends on 2) The method of claim 2, wherein the reconfiguring comprises: selecting a Logical Block Address (LBA) range for reconfiguring a subset of cache blocks; locking a stripe associated with the subset of cache blocks to deny access to the subset of cache blocks that are being re-configured; associating each of the subset of cache blocks with hash buckets of the hashing data structure based on the second hash index value; and unlocking the stripe associated with the subset of cache blocks. ### Claim 4 (depends on 3) The method of claim 3, further comprising: tracking a reconfiguration boundary that indicates which cache blocks have been reconfigured for processing I/O requests using either the first hash index value or the second hash index value. ### Claim 5 (depends on 1) The method of claim 1, further comprising: determining a subset of cache blocks within a set of cache blocks associated with a new I/O request; and processing the new I/O request using the second hash index value when reconfiguration has been completed for the subset of cache blocks. ### Claim 6 (depends on 5) The method of claim 5, further comprising: processing the new I/O request using the first hash index value, when reconfiguration has not been started for the subset of cache blocks. ### Claim 7 (depends on 6) The method of claim 6, further comprising: queueing the new I/O request until a lock has been released indicating that reconfiguration has been completed for the subset of cache blocks. ### Claim 8 A non-transitory machine readable medium having stored thereon instructions for performing a method comprising machine executable code which when executed by at least one machine, causes the machine to: analyze a plurality of input/output (I/O) requests to determine a pattern indicating if the I/O requests are random or sequential; and use the pattern for dynamically changing a first input to a second input for computing a hash index value by a hashing function that is used to index into a hashing data structure to look up a cache block to cache an I/O request to read or write data; wherein for random I/O requests, a segment size is the first input to a hashing function to compute a first hash index value and for sequential I/O requests, a stripe size is used as the second input for computing a second hash index value. ### Claim 9 (depends on 8) The non-transitory machine readable medium of claim 8, wherein the instructions further cause the machine to: reconfigure a set of cache blocks when input to the hashing function changes from the first input to the second input, where one or more of the set of cache blocks remain accessible using the first hash index value and one or more of the set of cache blocks is accessible using the second hash index value. ### Claim 10 (depends on 9) The non-transitory machine readable medium of claim 9, wherein the reconfiguration comprises: selecting a Logical Block Address (LBA) range for reconfiguring a subset of cache blocks; locking a stripe associated with the subset of cache blocks to deny access to the subset of cache blocks that are being re-configured; associating each of the subset of cache blocks with hash buckets of the hashing data structure based on the second hash index value; and unlocking the stripe associated with the subset of cache blocks. ### Claim 11 (depends on 10) The non-transitory machine readable medium of claim 10, wherein the reconfiguration further comprises: tracking a reconfiguration boundary that indicates which cache blocks have been reconfigured for processing I/O requests using either the first hash index value or the second hash index value. ### Claim 12 (depends on 8) The non-transitory machine readable medium of claim 8, wherein the instructions further cause the machine to: determine a subset of cache blocks within the set of cache blocks associated with a new I/O request; and process the new I/O request using the second hash index value when reconfiguration has been completed for the subset of cache blocks. ### Claim 13 (depends on 12) The non-transitory machine readable medium of claim 12, wherein the instructions further cause the machine to: process the new I/O request using the first hash index value, when reconfiguration has not been started for the subset of cache blocks. ### Claim 14 (depends on 13) The non-transitory machine readable medium of claim 13, wherein the instructions further cause the machine to: queue the new I/O request until a lock has been released indicating that reconfiguration has been completed for the subset of cache blocks. ### Claim 15 A system comprising: a memory containing machine readable medium comprising machine executable code having stored thereon instructions; and a processor coupled to the memory, the processor configured to execute the machine executable code to cause the processor to: analyze a plurality of input/output (I/O) requests to determine a pattern indicating if the I/O requests are random or sequential; and use the pattern for dynamically changing a first input to a second input for computing a hash index value by a hashing function that is used to index into a hashing data structure to look up a cache block to cache an I/O request to read or write data; wherein for random I/O requests, a segment size is the first input to a hashing function to compute a first hash index value and for sequential I/O requests, a stripe size is used as the second input for computing a second hash index value. ### Claim 16 (depends on 15) The system of claim 15, wherein the processor further executes the machine executable code to: reconfigure a set of cache blocks when input to the hashing function changes from the first input to the second input, where one or more of the set of cache blocks remain accessible using the first hash index value and one or more of the set of cache blocks is accessible using the second hash index value. ### Claim 17 (depends on 16) The system of claim 16, wherein the reconfiguration comprises: selecting a Logical Block Address (LBA) range for reconfiguring a subset of cache blocks; locking a stripe associated with the subset of cache blocks to deny access to the subset of cache blocks that are being re-configured; associating each of the subset of cache blocks with hash buckets of the hashing data structure based on the second hash index value; and unlocking the stripe associated with the subset of cache blocks. ### Claim 18 (depends on 17) The system of claim 17, wherein the reconfiguration further comprises: tracking a reconfiguration boundary that indicates which cache blocks have been reconfigured for processing I/O requests using either the first hash index value or the second hash index value. ### Claim 19 (depends on 15) The system of claim 15, wherein the processor further executes the machine executable code to: determine a subset of cache blocks within the set of cache blocks associated with a new I/O request; and process the new I/O request using the second hash index value when reconfiguration has been completed for the subset of cache blocks. ### Claim 20 (depends on 19) The system of claim 19, wherein the processor further executes the machine executable code to: process the new I/O request using the first hash index value, when reconfiguration has not been started for the subset of cache blocks. ### Claim 21 (depends on 20) The system of claim 20, wherein the processor further executes the machine executable code to: queue the new I/O request until a lock has been released indicating that reconfiguration has been completed for the subset of cache blocks.