Cuckoo hashing including accessing hash tables using affinity table

Patent metadata

Field	Value
Publication number	US-11782895-B2
Application number	US-202017013697-A
Country	US
Kind code	B2
Filing date	Sep 7, 2020
Priority date	Sep 7, 2020
Publication date	Oct 10, 2023
Grant date	Oct 10, 2023

Abstract

A hashing apparatus includes a memory and circuitry. The memory stores (i) multiple hash tables storing associative entries, each including at least one entry key and a respective value, the hash tables are associated with respective different hash functions, and an associative entry is accessible by applying the relevant hash function to a key matching an entry key in the associative entry, and (ii) an affinity table that stores table-selectors for selecting hash tables with which to start a key lookup. The circuitry receives a key, reads from the affinity table, by applying an affinity function to the key, a table-selector that selects a hash table, accesses in the selected hash table an associative entry by applying the hash function associated with the selected hash table to the key, and in response to detecting that the key matches an entry key in the associative entry, outputs the respective value.

First claim

The invention claimed is:

1. A hashing apparatus, comprising a memory and circuitry,
wherein the memory is to hold:
multiple hash tables, comprising associative entries each comprising at least one respective entry key and a respective value, wherein the hash tables are associated with respective hash functions, wherein associative entries in a given hash table are accessible by applying the hash function corresponding to the given hash table to respective keys being searched; and
an affinity table, comprising multiple table-selectors, each table selector selecting one of the hash tables with which a search for a searched key is to begin; and

wherein the circuitry is to:
receive a key to be searched;
read from the affinity table, by applying an affinity function to the key, a table-selector that selects a first hash table from among the multiple hash tables;
attempt matching the key to entry keys in the first hash table;
in response to detecting that the key matches an entry key in the first hash table, output the value corresponding to the matching entry key; and
in response to detecting that a given key matches an entry key in a second hash table, different from the first hash table that was selected by the affinity table, make a subsequent search for the given key faster, by updating the table-selector in the affinity table to select the second hash table instead of the first hash table.

2. The hashing apparatus according to claim 1 , wherein the affinity function comprises a dedicated hash function.

3. The hashing apparatus according to claim 1 , wherein the circuitry is to, in response to detecting that the key being searched fails to match the entry key, attempt matching the key to another entry key in another hash table by applying to the key the hash function corresponding to the another hash table.

4. The hashing apparatus according to claim 1 , wherein the circuitry is to, in response to detecting that a certain key matches an entry key in a given associative entry stored in a third hash table, but the table-selector of the certain key in the affinity table points to a fourth different hash table, move one or more associative entries among the hash tables so as to improve key search performance.

5. The hashing apparatus according to claim 4 , wherein, the circuitry is to, in response to detecting that a location corresponding to the certain key in the fourth hash table is available, move the given associative entry to the location in the fourth hash table.

6. The hashing apparatus according to claim 4 , wherein, the circuitry is to, in response to detecting that a location corresponding to the certain key in the fourth hash table is unavailable, move an associative entry from the location to another hash table, and move the given associative entry to the location in the fourth hash table.

7. The hashing apparatus according to claim 4 , wherein the circuitry is to move the given associative entry from the third hash table to another hash table so that starting a key lookup with the another hash table is faster than with the third hash table.

8. The hashing apparatus according to claim 1 , wherein the circuitry comprises multiple lookup engines assigned respectively the multiple hash tables, wherein the circuitry is to receive multiple keys, to retrieve from the affinity table multiple respective table-selectors in parallel, and based on the retrieved table-selectors, to distribute one or more of the received keys to respective one or more lookup engines, for parallel key lookup.

9. The hashing apparatus according to claim 8 , wherein the circuitry is to forward a key that fails matching in a given hash table using a respective lookup engine for lookup by another lookup engine.

10. The hashing apparatus according to claim 8 , wherein the circuitry is to operate in synchronization with a clock source, and wherein each of the lookup engines is to search, in each clock cycle of the clock source, (i) a key not yet searched by any of the lookup engines, or (ii) a key that has failed matching in another lookup engine.

11. The hashing apparatus according to claim 1 , wherein the associative entry comprises multiple entry keys and respective values, and wherein the circuitry is to check whether the key matches any of the multiple entry keys, and in response to detecting that the key matches an entry key among the multiple entry keys in the associative entry, to output the value corresponding to the matching entry key.

12. A method, comprising:
in an apparatus comprising a memory that holds (i) multiple hash tables comprising associative entries each comprising at least one respective entry key and a respective value, wherein the hash tables are associated with respective hash functions, and wherein associative entries in a given hash table are accessible by applying the hash function corresponding to the given hash table to respective keys being searched; and
an affinity table comprising multiple table-selectors, each table selector selecting one of the hash tables with which a search for a searched key is to begin, the method comprising:
receiving a key to be searched;
reading from the affinity table, by applying an affinity function to the key, a table-selector that selects a first hash table from among the multiple hash tables;
attempting matching the key to entry keys in the first hash table;
in response to detecting that the key matches an entry key in the first hash table, outputting the value corresponding to the matching entry key; and
in response to detecting that a given key matches an entry key in a second hash table, different from the first hash table that was selected by the affinity table, making a subsequent search for the given key faster, by updating the table-selector in the affinity table to select the second hash table instead of the first hash table.

13. The method according to claim 12 , wherein the affinity function comprises a dedicated hash function.

14. The method according to claim 12 , and comprising, in response to detecting that the key being searched fails to match the entry key, attempting to match the key to another entry key in another hash table by applying to the key the hash function corresponding to the another hash table.

15. The method according to claim 12 , and comprising, in response to detecting that a certain key matches an entry key in a given associative entry stored in a third hash table, but the table-selector of the certain key in the affinity table points to a fourth different hash table, moving one or more associative entries among the hash tables so as to improve key search performance.

16. The method according to claim 15 , and comprising, in response to detecting that a location corresponding to the certain key in the fourth hash table is available, moving the given associative entry to the location in the fourth hash table.

17. The method according to claim 15 , and comprising, in response to detecting that a location corresponding to the certain key in the fourth hash table is unavailable, moving an associative entry from the location to another hash table, and moving the given associative entry to the location in the fourth hash table.

18. The method according to claim 15 , and comprising moving the given associative entry from the third hash table to another hash table so that starting a key lookup with the another hash table is faster than with the third hash table.

19. The method according to claim 12 , wherein the apparatus comprises multiple lookup engines assigned r

Assignees

• Mellanox Tech Tlv Ltd
• Mellanox Technologies Ltd

Inventors

• Levy Aviad
• Levy Gil
• Reviriego Pedro
• Pontarelli Salvatore

Classifications

• G06F16/2255 Primary

  Hash tables · CPC title

• G06F1/12

  Synchronisation of different clock signals {provided by a plurality of clock generators} · CPC title

• G06F16/9014

  hash tables · CPC title

• H04L45/7453

  using hashing · CPC title