HASH-TABLE LOOKUP WITH CONTROLLED LATENCY

• US 20200136971A1
• Filed: 12/26/2019
• Published: 04/30/2020
• Est. Priority Date: 06/07/2019
• Status: Active Application

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: COHEN, Elazar
• Application Number:
  US16/727,685
• Publication Number:
  US 20200136971A1
• Time in Patent Office: Days
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/0833 involving conference or group key network architectures or network communication protocols for key management in group communication in a packet data network H04L63/065
• CPC Class Codes: H04L 9/3239 involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

Examples described herein relate to key-value lookups. A first index is calculated based on a first hash function and a received key. A first hash table including entries associated with a first hash calculation on a key is accessed. A collision hint table is accessed to identify any other hash table to search. If the collision hint table indicates any other table to search, the first hash table and the any other hash table are searched to identify an entry associated with an index that matches the first index.

Claims

1. An apparatus for key-value lookup comprising:

a first memory to store a first hash table that comprises entries associated with a first hash calculation on a received key, wherein an entry includes a key and the first memory is to provide the entry based on a match of an associated key with the received key, wherein a first index is based on a first hash function and a received key and

a processor to retrieve a collision hint to identify any other hash table to search and to cause search of any other hash table in parallel for a match of a hash of the key.

2. The apparatus of claim 1, wherein a key-value lookup occurs in a determinate time frame.

3. The apparatus of claim 1, comprising a hint content addressable memory (CAM) to store the collision hints wherein collision hints identify zero or more other hash tables that are to be searched.

4. The apparatus of claim 1, wherein the first memory is to store collision hints wherein the collision hints identify zero or more other hash tables that are to be searched.

5. The apparatus of claim 1, comprising:

a second hash function calculator to calculate a second index based on a second hash function and the received key based on a collision hint identifying another hash table to search and

a second memory to store a second hash table and to provide an entry that includes an index that matches the second index.

6. The apparatus of claim 5, wherein the second hash function calculation is to produce a different index than that of the first hash calculation on the received key.

7. The apparatus of claim 1, comprising a hint content addressable memory (CAM) to store the collision hints wherein collision hints identify zero or more other hash tables that are to be searched, wherein the search for entries in the first hash table for a match of the key and the search of any other hash table for a match of the received key occurs within a single memory read cycle.

8. The apparatus of claim 1, wherein the first memory is to store the collision hints, wherein collision hints identify zero or more other hash tables that are to be searched and wherein the search for entries in the first hash table for a match of the key and the search of any other hash table for a match of the received key occur within a duration of two memory read cycles.

9. The apparatus of claim 1, comprising one or more of:

a network interface controller, server, rack, or data center.

10. The apparatus of claim 1, comprising a network interface controller to use key-value lookup to determine a packet processing action on a packet.

11. A method comprising:

accessing a collision hint table to identify any other hash tables aside from a default table to search, wherein an entry in a table includes a key-value pair and a table is to provide the entry based on a match of an associated key with a received key;

calculating an index using a hash function and the received key based on the collision hint table identifying another hash table to search; and

providing a value from an entry from the another hash table based on a match of the received key with a key in the entry from the another hash table.

12. The method of claim 11, comprising accessing a content addressable memory (CAM) to access the collision hint table.

13. The method of claim 11, wherein a default hash table is to store the collision hint table.

14. The method of claim 11, comprising:

calculating an index based on a hash calculation and the received key based on a collision hint identifying another hash table to search and

accessing a hash table identified by the collision hint and providing an entry that includes an index that matches the calculated index.

15. The method of claim 11, comprising searching a default hash table for a match of the received key, wherein searching for entries in the default hash table for the match of the key and searching of any other hash table for a match of the received key occurs within a single memory read cycle.

16. The method of claim 11, comprising searching a default hash table for a match of the received key, wherein searching for entries in the default hash table for the match of the key and searching of any other hash table for a match of the received key occurs within a single memory read cycle.

17. The method of claim 11, wherein hash calculations performed for different tables using the received key produce different indexes.

18. A network interface comprising:

a first memory to store a first hash table comprising entries associated with a first hash calculation on a received key and to store a collision hint to identify any other hash table to search, wherein an entry includes a key-value pair and the first memory is to provide the value based on a match of the received key with the key of the key-value pair and

a set of hash function calculators to calculate a set of indexes based on a set of hash functions and the received key based on a collision hint identifying at least one other hash table to search, the hash functions to yield different indexes for the received key.

19. The network interface of claim 18, comprising a content addressable memory (CAM) to store collision hints, wherein collision hints identify zero or more other hash tables that are to be searched for the received key.

20. The network interface of claim 19, wherein the first memory is to store collision hints, wherein collision hints identify zero or more other hash tables that are to be searched for the received key.