Proxy hash table

Patent metadata

Field	Value
Publication number	US-11080252-B1
Application number	US-201916271669-A
Country	US
Kind code	B1
Filing date	Feb 8, 2019
Priority date	Oct 6, 2014
Publication date	Aug 3, 2021
Grant date	Aug 3, 2021

Abstract

Some embodiments of the invention provide novel methods for storing data in a hash-addressed memory and retrieving stored data from the hash-addressed memory. In some embodiments, the method receives a search key and a data tuple. The method then uses a first hash function to generate a first hash value from the search key, and then uses this first hash value to identify an address in the hash-addressed memory. The method also uses a second hash function to generate a second hash value, and then stores this second hash value along with the data tuple in the memory at the address specified by the first hash value. To retrieve data from the hash-addressed memory, the method of some embodiments receives a search key. The method then uses the first hash function to generate a first hash value from the search key, and then uses this first hash value to identify an address in the hash-addressed memory. At the identified address, the hash-addressed memory stores a second hash value and a data tuple. The method retrieves a second hash value from the memory at the identified address, and compares this second hash value with a third hash value that the method generates from the search key by using the second hash function. When the second and third hash values match, the method retrieves the data tuple that the memory stores at the identified address.

First claim

What is claimed is:

1. A method of accessing a data storage device, the method comprising:
using first and second hash functions to generate respective first and second hash values from a search key;
using the first hash value to identify an address in a hash-addressed memory that stores a third hash value and a data tuple;
determining whether the second and third hash values match, wherein determining whether the second and third hash values match comprises determining whether the second hash value matches a transformed version of the third hash value; and
based on the second and third hash values matching, outputting the data tuple from the data storage device, wherein the data storage device stores the third hash value and the data tuple.

2. The method of claim 1 , wherein the first and second hash values differ as the first and second hash functions differ.

3. The method of claim 1 , wherein the hash-addressed memory comprises N sub-tables of an N-way hash table.

4. The method of claim 3 , wherein the first hash value identifies N addressable locations in the N sub-tables of the N-way hash table.

5. The method of claim 1 , wherein determining whether the second and third hash values match comprises determining whether the second hash value is an inverted version of the third hash value.

6. The method of claim 1 , wherein the search key comprises a portion of a header value, the header value comprises a portion of a header of a received packet, and the header value comprises one or more of: a source IP address, destination IP address, source port, destination port, and protocol.

7. The method of claim 1 , wherein the data tuple comprises a destination IP address (DIP) of a destination node.

8. A data storage comprising:
first and second hash generators to generate respective first and second hash values from a search key;
a hash-addressed memory to store a plurality of data tuples with a plurality of hash values at a plurality of locations, and to output (i) a third hash value that is stored at a location identified by the first hash value at the hash-addressed memory in the data storage, and (ii) a data tuple that is stored with the third hash value at the hash-addressed memory in the data storage; and
a comparator to compare the second hash value and the third hash value, and to output the data tuple from the data storage based on a match of the second and third hash values, wherein the second and third hash values match if the second hash value matches a transformed version of the third hash value.

9. The data storage of claim 8 , wherein the first and second hash values differ as first and second hash functions differ.

10. The data storage of claim 8 , wherein the hash-addressed memory comprises N sub-tables of an N-way hash table.

11. The data storage of claim 10 , wherein the first hash value identifies N addressable locations in the N sub-tables of the N-way hash table.

12. The data storage of claim 8 , wherein the second and third hash values match when the second hash value is an inverted version of the third hash value.

13. The data storage of claim 8 , wherein the search key comprises a portion of a header value, the header value comprises a portion of a header of a received packet, and the header value comprises one or more of: a source IP address, destination IP address, source port, destination port, and protocol.

14. The data storage of claim 8 , wherein the data tuple comprises a destination IP address (DIP) of a destination node.

Assignees

• Barefoot Networks Inc

Inventors

• Bosshart Patrick
• Kim Changhoon

Classifications

• G06F16/137 Primary

  Hash-based (content-based indexing of textual data G06F16/31) · CPC title

• G06F3/064

  Management of blocks · CPC title

• G06F3/0604

  Improving or facilitating administration, e.g. storage management · CPC title

• G06F16/9014

  hash tables · CPC title

• G06F3/0659

  Command handling arrangements, e.g. command buffers, queues, command scheduling · CPC title