Proxy hash table

Patent metadata

Field	Value
Publication number	US-9529531-B2
Application number	US-201414507811-A
Country	US
Kind code	B2
Filing date	Oct 6, 2014
Priority date	Oct 6, 2014
Publication date	Dec 27, 2016
Grant date	Dec 27, 2016

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 storing a data tuple that is associated with a search key in a hash-addressed memory, the method comprising:
using a first hash function to generate a first hash value from the search key;
using the first hash value to identify an address in the hash-addressed memory, said hash-addressed memory comprising a plurality of hash tables;
using a second hash function to generate a second hash value from the search key;
iteratively examining the plurality of hash tables according to a hash-table order, in order to identify a hash table in the plurality of hash tables that does not store the second hash value; and
storing the second hash value and the data tuple in the identified hash table, that does not store the second hash value, the identified address.

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 plurality of hash-tables 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. A method of storing a data tuple that is associated with a search key in a hash-addressed memory, the method comprising:
using a first hash function to generate a first hash value from the search key;
using the first hash value to identify an address in the hash-addressed memory, said hash-addressed memory comprising a plurality of hash tables;
using a second hash function to generate a second hash value from the search key;
determining whether the second hash value is stored in a first hash table that is first according to an order of the hash tables;
when the second hash value is not stored in the first hash table, storing the second hash value and the data tuple in the first hash table; and
when the second hash value is stored in the first hash table, determining whether the second hash value is stored in a second hash table that is second according to the hash-table order.

6. The method of claim 5 , wherein the plurality of hash-tables comprises N sub-tables of an N-way hash table.

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

8. The method of claim 1 , wherein iteratively examining the plurality of hash tables according to a hash-table order, in order to identify a hash table in the plurality of hash tables that does not store the second hash value comprises:
determining whether the second hash value is stored in a first hash table that is first according to an order of the hash tables;
when the second hash value is not stored in the first hash table, identifying the first hash table as the hash table that does not store the second hash value;
when the second hash value is stored in the first hash table, sequentially examining the other hash tables according to the hash-table order; and
when a particular hash table is determined to not store the second hash value, identifying the particular hash table as the hash table that does not store the second hash value.

9. A non-transitory machine readable medium storing a program that stores a data tuple that is associated with a search key in a hash-addressed memory, the program comprising sets of instructions for:
using a first hash function to generate a first hash value from the search key;
using the first hash value to identify an address in the hash-addressed memory, said hash-addressed memory comprising a plurality of hash tables;
using a second hash function to generate a second hash value from the search key;
determining whether the second hash value is stored in a first hash table that is first according to a hash-table order;
when the second hash value is not stored in the first hash table, storing the second hash value and the data tuple in the first hash table at the identified address;
when the second hash value is stored in the first hash table, determining whether the second hash value is stored in a second hash table that is second according to the hash-table order; and
when the second hash value is not stored in the second hash table, storing the second hash value and the data tuple in the second hash table at the identified address.

10. The machine readable medium of claim 9 , wherein the program further comprises sets of instructions for:
when the second hash value is stored in the first and second hash tables, iteratively examining additional hash tables in a plurality of remaining hash tables according to the hash-table order to determine whether the second hash value is stored in all the hash tables in the plurality of remaining hash tables;
storing the second hash value and the data tuple at the identified address in a particular hash table of the plurality of remaining hash tables when the particular hash table is identified as a hash table that does not store the second hash value; and
when the second hash value is stored in all of the plurality of hash tables, storing the second hash value and the data tuple in another data structure that is not a hash table.

11. A method of retrieving a data tuple from a hash-addressed memory that stores a plurality of data tuples for a plurality of search keys, the method comprising:
from a received search key, generating a first hash value and a second hash value;
retrieving a third hash value from the memory at an address identified by the first hash value, wherein a data tuple is stored at the identified address along with the third hash value;
comparing the second and third hash values; and
when the second and third hash values have a particular relationship with each other, outputting the data tuple from the memory,
wherein the hash-addressed memory comprises a plurality of hash tables,
wherein retrieving the third hash value comprises iteratively examining the hash tables according to a sequence in order to identify a first hash table in the sequence that stores the second hash value at an addressed location in the first hash table that is identified by the first hash value.

12. The method of claim 11 further comprising:
using a first hash function to generate the first hash value; and
using a second hash function to generate the second hash value;
wherein the first and second hash values differ as the first and second hash functions differ.

13. The method of claim 11 , wherein outputting the data tuple comprises outputting the data tuple when the second and third hash values are identical.

14. The method of claim 11 , wherein outputting the data tuple comprises outputting the data tuple when the second hash value is an inverted version of the third hash value.

15. The method of claim 11 , wherein outputting the data tuple comprises outputting the data tuple when the second hash value is a transformed version of the third hash value.

16. The method of claim 11 , wherein the plurality of hash tables comprises an N-way hash table comprising N sub-tables, wherein the first hash value identifies N addressable locations in the N sub-tables of the hash table.

17. The method of claim 11 , wherein the outputted data tuple comprises data identifying a different storage structure from which further information is to be retrieved.

18. A connection data storage for retrieving a data tuple, the data storage comprising:
first and second hash generators for generating first and second hash values from a received search key;
a hash-addressed memory comprising a plurality of hash tables

Assignees

• Barefoot Networks Inc

Inventors

• Bosshart Patrick
• Kim Changhoon

Classifications

• G06F3/0604 Primary

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

• G06F3/064

  Management of blocks · CPC title

• G06F3/0673

  Single storage device · CPC title

• G06F3/0659

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

• G06F16/137 Primary

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