Pattern Matching Technique

• US 20100095064A1
• Filed: 10/14/2008
• Published: 04/15/2010
• Est. Priority Date: 10/14/2008
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: Cache Iq
• Inventors: Aviles, Joaquin J.
• Granted Patent: US 8,103,764 B2
• Time in Patent Office: Days
• US Class Current: 711/118
• 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/5682 Policies or rules for updating, deleting or replacing the stored data

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 perfect hashing memory index technique to rapidly detect predetermined patterns in received packet payloads and retrieve matching patterns from memory by generating a data structure pointer and index offset to directly address the pattern in the datagram memory, thereby accelerating evaluation of the packet with the matching pattern by the host processor.

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;

a payload memory for storing payload data for one or more packet flows;

a packet processor coupled to the cache memory, the payload 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 comprises a pattern detection module configured to find a matching pattern by scanning a received packet for one or more predetermined trigger patterns and generating a direct memory address for the matching pattern in memory; and

a host processor coupled to the packet processor and the payload memory, where the host processor uses the direct memory address to directly retrieve the matching pattern from memory and applies a cache policy profile to the matching pattern to make a caching decision for a data cache request associated with the matching pattern.

2. The standalone cache unit of claim 1, where the direct memory address comprises a data structure pointer which addresses the matching pattern in a local memory of the host processor.

3. The standalone cache unit of claim 1, where the direct memory address comprises a datagram address and an index offset, where the datagram address points to a starting address for an addressed datagram structure which stores payload data for a specified packet flow, and where the index offset points to an offset within the addressed datagram structure where the matching pattern is located.

4. The standalone cache unit of claim 1, where the pattern detection module comprises a perfect hashing memory inspection module for scanning the entirety of the data payload from every received packet.

5. The standalone cache unit of claim 4, where the perfect hashing memory inspection module comprises:

a shift circuit for receiving a plurality of packets and outputting in parallel a selected subset of data bits from the received packets;

a hash circuit for hashing the selected subset of data bits to generate a pattern ID of a possible match from the selected subset of data bits;

a mapping circuit for mapping the pattern ID to a length value and an address value for retrieving a trigger pattern to be compared to the selected subset of data bits from the received packets;

a memory circuit for storing a plurality of trigger patterns, where each trigger pattern is addressed by an address value generated by the mapping circuit;

a circuit for comparing a trigger pattern retrieved from the memory circuit with the selected subset of data bits from the received packets and generating a match signal if the selected subset of data bits matches the trigger pattern retrieved from the memory circuit; and

an output circuit for outputting the direct memory address when there is a match between the selected subset of data bits and the trigger pattern retrieved from the memory circuit.

6. The standalone cache unit of claim 5, where the shift circuit comprises a serial-in parallel-out shift register.

7. The standalone cache unit of claim 5, where the hash circuit comprises a Merkle type hash tree table.

8. The standalone cache unit of claim 5, where the mapping circuit comprise a lookup table which is indexed by a pattern ID value to output a length value and an address value corresponding to the pattern ID value.

9. The standalone cache unit of claim 5, where memory circuit comprises a pattern memory lookup table that is indexed by an address value to output a trigger pattern and a corresponding data structure pointer.

10. The standalone cache unit of claim 5, further comprising an index offset generator circuit for combining a sequence number from a first packet having a first data payload in which a matching pattern is detected with an offset value from the beginning of a first data payload to the first character of the matched pattern.

11. The standalone cache unit of claim 5, further comprising a data structure pointer generator circuit for generating address information that corresponds to the matching trigger pattern and that is used to locate a copy of the matching trigger pattern in a local memory of the host processor.

12. The standalone cache unit of claim 11, where the address information comprises the pattern ID, the address value or the matching trigger pattern.

13. A pattern search method for retrieving a matching trigger pattern from memory that matches a pattern contained in a data packet, comprising:

receiving a data packet which contains a pattern comprising a plurality of data segments;

hashing one or more data segments from the received data packet to generate a pattern identifier which is used to retrieve one of a plurality of trigger patterns from a first memory;

comparing a retrieved trigger pattern from the first memory with the plurality of data segments from the received data packet to determine if the retrieved trigger pattern is a matching trigger pattern that matches at least part of the plurality of data segments; and

generating a direct memory address for use by a host processor in locating a copy of the matching trigger pattern in a second memory.

14. The pattern search method of claim 13, further comprising storing a plurality of trigger patterns in the first memory, where each trigger pattern is addressed within the first memory by an address that is generated at least in part by hashing one or more data segments from the received data packet.

15. The pattern search method of claim 13, where hashing one or more data segments comprises applying a perfect hashing memory scheme to detect one of the plurality of trigger patterns in the received plurality of data segments.

16. The pattern search method of claim 13, where generating a direct memory address comprises generating a data structure pointer for retrieving a copy of the matching trigger pattern in a local memory of the host processor.

17. The pattern search method of claim 13, where generating a direct memory address comprises generating a datagram address and an index offset, where the datagram address points to a starting address for an addressed datagram structure in a data payload memory which stores payload data for a specified packet flow, and where the index offset points to an offset within the addressed datagram structure where a copy of the matching trigger pattern is located.

18. The pattern search method of claim 13, where generating a direct memory address comprises generating first and second direct memory addresses for retrieving first and second copies of the matching trigger pattern from the second memory and a third memory, respectively.

19. The pattern search method of claim 18, further comprising:

comparing the first and second copies of the matching trigger pattern to one another to determine if there is a match; and

applying a cache policy profile to make a caching decision for a data cache request associated with the matching trigger pattern.

20. A method for accelerating data storage cache access, comprising:

storing a plurality of trigger patterns in a first memory;

applying a reconfigurable perfect hash matching scheme to a received data packet to identify a matching trigger pattern from the plurality of trigger patterns, where the matching trigger pattern matches a data pattern contained in the received data packet;

generating a direct memory address for use by a host processor in locating a copy of the matching trigger pattern in a second memory; and

applying a cache policy profile to the copy of the matching trigger pattern from the second memory to make a caching decision for a data cache request associated with the matching trigger pattern.