Dual Hash Indexing System and Methodology

• US 20100023726A1
• Filed: 07/28/2008
• Published: 01/28/2010
• Est. Priority Date: 07/28/2008
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: Cache Iq
• Inventors: Aviles, Joaquin J.
• Granted Patent: US 7,979,671 B2
• Time in Patent Office: Days
• US Class Current: 711/216
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching

Abstract

A method, system and program are disclosed for accelerating data storage in a cache appliance that transparently monitors NFS and CIFS traffic between clients and NAS subsystems and caches files in a cache memory by using a dual hash technique to rapidly store and/or retrieve connection state information for cached connections in a plurality of index tables that are indexed by hashing network protocol address information with a pair of irreducible CRC hash algorithms to obtain an index to the memory location of the connection state information.

Claims

1. A standalone cache unit for caching data operations requested from one or more networked data storage devices by one or more remote clients, the standalone cache unit comprising:

a cache memory for caching data that is requested by a remote client, the cache memory storing a plurality of index tables and a connection state table for each connection used to cache data in the cache memory;

a packet processor coupled to the cache memory and to one or more I/O ports for transparently splicing connections between the data storage devices and remote clients, where the packet processor inspects network protocol traffic state parameters received on the I/O ports to determine if a request from a remote client can be serviced by the standalone cache unit by extracting connection information from each received packet and generating first and second hash values from the connection information, where the first hash value is used to point to an addressed index table from the plurality of index tables, and where the second hash value is stored as an index to an entry in the addressed index table which also stores a connection data index value which is used to point to an address for the connection state table corresponding to the received packet.

2. The standalone cache unit of claim 1, where each of the plurality of index tables comprises a plurality of entries, where each entry comprises an index portion which stores a second hash value computed from one of the cached connections, and an output portion which stores a connection data index value which is used to point to an address for the connection state table corresponding to the received packet.

3. The standalone cache unit of claim 1, where the packet processor extracts connection information by extracting an n-tuple from each received packet.

4. The standalone cache unit of claim 1, where the packet processor extracts connection information by assembling at least a source IP address (SIP) segment, a destination IP address (DIP) segment, a source transport port (SP) segment, and a destination transport port (DP) segment from each received packet.

5. The standalone cache unit of claim 1, where the packet processor generates first and second hash values from the connection information by applying two irreducible CRC hash functions to the connection information.

6. The standalone cache unit of claim 1, where the first hash value is used to point to an addressed index table by shifting the first hash value by a predetermined number of bit positions.

7. The standalone cache unit of claim 1, where the connection data index value is used to point to an address for the connection state table by shifting the connection data index value by a predetermined number of bit positions.

8. The standalone cache unit of claim 1, where the packet processor executes software that transparently monitors NFS and CIFS traffic between remote clients and NAS subsystems.

9. A method for retrieving connection information from a memory, comprising:

determining a first connection identifier from a received packet for retrieving connection information corresponding to the received packet;

generating a first memory address for a first table in memory corresponding to the first connection identifier by calculating a first hash value from the first connection identifier;

generating a first index to the first table corresponding to the first connection identifier by calculating a second hash value from the first connection identifier;

retrieving from the first table a first entry using the first index; and

generating from the first entry a second memory address for retrieving connection information from a connection state table in memory corresponding to the first connection.

10. The method of claim 9, where determining the first connection identifier comprises extracting an n-tuple from each received packet.

11. The method of claim 9, where determining the first connection identifier comprises extracting at least a source IP address (SIP) segment, a destination IP address (DIP) segment, a source transport port (SP) segment, and a destination transport port (DP) segment from each received packet.

12. The method of claim 9, where the first and second hash values are calculated by applying two irreducible CRC hash functions to the first connection identifier.

13. The method of claim 9, where generating the first memory address comprises shifting the first hash value by a predetermined number of bit positions.

14. The method of claim 9, where generating the first memory address comprises calculating a first 18-bit hash value and then shifting the first 18-bit hash value by four bit positions.

15. The method of claim 9, where generating the first index comprises shifting the second hash value by a predetermined number of bit positions.

16. The method of claim 9, where generating the first index comprises calculating a second 18-bit hash value and then shifting the second 18-bit hash value by four bit positions.

17. A method for storing connection information in memory, comprising:

determining a first connection identifier from a received packet for storing connection information corresponding to the received packet;

generating a first memory address for a first table in memory corresponding to the first connection identifier by calculating a first hash value from the first connection identifier;

generating a first index to the first table corresponding to the first connection identifier by calculating a second hash value from the first connection identifier;

generating a unique identifier;

storing the first index and the unique identifier in an available entry in the first table located at the first memory address; and

storing connection information at a second memory address in a connection state table in memory corresponding to the first connection, where the second memory address is generated from the unique identifier.

18. The method of claim 17, where determining the first connection identifier comprises extracting an n-tuple from each received packet.

19. The method of claim 17, where the first and second hash values are calculated by applying two irreducible CRC hash functions to the first connection identifier.

20. The method of claim 17, where generating a first memory address comprises applying a first irreducible CRC polynomial hash function=X0̂

X1̂

X13̂

X17̂

X18 to the first connection identifier, and where generating a first index comprises applying a second irreducible CRC polynomial hash function=X0̂

X1̂

X3̂

X5̂

X7̂

X17̂

X18 to the first connection identifier.