Methods and systems for dynamic hashing in caching sub-systems

Patent metadata

Field	Value
Publication number	US-10481835-B2
Application number	US-201414510829-A
Country	US
Kind code	B2
Filing date	Oct 9, 2014
Priority date	Oct 9, 2014
Publication date	Nov 19, 2019
Grant date	Nov 19, 2019

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.

First claim

What is claimed is:

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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

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.

16. 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.

17. 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.

18. 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.

19. The system of claim 15 , wherein the processor f

Assignees

• Netapp Inc

Inventors

• Banerjee Arindam
• Humlicek Donald R

Classifications

• G06F3/067 Primary

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F3/0638

  Organizing or formatting or addressing of data · CPC title

• G06F3/0611

  in relation to response time · CPC title

• G06F12/0868 Primary

  Data transfer between cache memory and other subsystems, e.g. storage devices or host systems · CPC title