Search

EP-4290821-B1 - EFFICIENT HASH TABLE LOOKUP

EP4290821B1EP 4290821 B1EP4290821 B1EP 4290821B1EP-4290821-B1

Inventors

  • JIANG, Weiwei
  • VADUVATHA, SRINIVAS
  • CHANDRA, PRASHANT R.
  • ZHENG, JIAZHEN
  • WALSH, Hugh McEvoy
  • WANG, WEIHUANG
  • AGARWAL, ABHISHEK

Dates

Publication Date
20260506
Application Date
20221116

Claims (11)

  1. A hash table system, comprising: a plurality of hash tables (20a-d), associated with respective hash functions (30a-d), for storing key-value pairs (150a); an overflow memory (50) for storing key-value pairs (150a) moved from the hash tables (20a-d) due to collision; and an arbiter (290), which is a weighted round-robin arbiter, for arbitrating among commands including update commands for installing key-value pairs (150a) into the hash tables (20a-d) or uninstalling key-value pairs (150a) from the hash tables (20a-d), match commands for matching keys to locations in the hash tables (20a-d), and rehash commands for relocating key-value pairs (150a) from the overflow memory (50) to the hash tables (20a-d) or relocating key-value pairs (150a) from one of the hash tables (20a-d) to another of the hash tables (20a-d), wherein a weight applied to the update commands and the match commands is varied according to an occupancy level of the overflow memory (50), and wherein the weight is set to a value associated with an occupancy region of two or more occupancy regions of the overflow memory (50), the occupancy region determined according to the occupancy level, and wherein for each system clock cycle, the arbiter selects as a selected command one of an update command, a match command, or a rehash command.
  2. The system according to claim 1, wherein each hash table (20a-d) comprises a plurality of buckets (40a), and each bucket (40a) comprises a plurality of cells (110a-d), wherein each cell (110a-d) is operable to store a key-value pair (150a), wherein each key hashes to one of the buckets (40a) in each hash table (20a-d), and wherein when the system performs an install operation for a key-value pair (150a), a bucket (40a) in each hash table (20a-d) is determined for the key-value pair (150a) to be stored by hashing the key with the respective hash functions (30a-d), and the key-value pair (150a) is stored in a hash-table for which the determined bucket is not full.
  3. The system according to claim 2, wherein when all of the buckets (40a) determined for a key-value pair (150a) to be stored are full, a key-value pair (150a) previously stored in one of the determined buckets (40a) is evicted and stored in the overflow memory (50), and the key-value pair (150a) to be stored is stored in the bucket (40a) from which the key-value pair (150a) previously stored is evicted
  4. The system according to any one of the preceding claims, wherein the overflow memory (50) is configured so that a location of a key-value pair (150a) stored in the overflow memory (50) is determined by searching for the key of the key-value pair (150a).
  5. The system according to claim 4, wherein the overflow memory (50) comprises a content addressable memory for storing keys of key-value pairs (150a), and another memory for storing values (130a) of the key-value pairs (150a).
  6. The system according to any one of the preceding claims, wherein the rehash commands comprise two types of rehash commands, a candidate generation type of rehash command for selecting a key-value pair (150a) as a candidate key-value pair for relocating and storing the candidate key-value pair in another memory, and a move type of rehash command for attempting to relocate a candidate key-value pair.
  7. The system according to claim 6, wherein move type rehash commands are prioritized over candidate generation type rehash commands.
  8. The system according to any one of claims 6 or 7, wherein when a plurality of keys corresponding to candidate key-value pairs (150a) is stored in one or more candidate memories and a move type rehash command is performed, a key for the move type rehash command is selected from the one or more candidate memories according to priority that prioritizes candidate keys corresponding to key-value pairs (150a) in the overflow memory (50) over candidate keys corresponding key-value pairs (150a) in the hash tables (20a-d).
  9. The system according to any one of claims 6 to 8, wherein when a plurality of keys corresponding to candidate key-value pairs (150a) is stored in one or more candidate memories and a move type rehash command is performed on a candidate key-value pair in the overflow memory (50) and fails, the candidate key-value pair is moved into a hash table location occupied by a selected key-value pair (150a), the selected key-value pair (150a) is moved into the overflow memory (50), and the key corresponding to the selected key-value pair (150a) is designated as a looped-back key, and is stored in the one or more candidate memories.
  10. The system according to claim 9, wherein when a plurality of keys corresponding to candidate key-value pairs (150a) is stored in one or more candidate memories and a move type rehash command is performed, the candidate key-value pair for the move type rehash command is selected according to a priority that prioritizes looped-back keys over non looped-back keys.
  11. The system according to any one of the preceding claims, wherein each of the key-value pairs (150a) comprises a connection identifier as a key and a cache memory address as a value (130a).

Description

BACKGROUND Content Addressable Memory architectures may be employed in systems that require rapid data search. Content Addressable Memories (CAMs) can be searched very quickly due to their parallel nature. However, CAMs are expensive in terms of chip area and power consumption. Accordingly, for many applications CAMs are impractical. US 2005/141519 A1 discloses that Internet Protocol address prefixes are hashed into hash tables allocated memory blocks on demand after collisions occur for both a first hash and a single rehash. US 2007/286194 A1 discloses a device and a method for processing a data packet. US 2019/238459 A1 discloses a method for operating a network device. EP 3 057 272 A1 discloses technologies for supporting concurrency of a flow lookup table at a network device. BRIEF SUMMARY The claimed subject-matter is defined in the independent claims. The dependent claims define embodiments thereof. It has been recognized that in many applications replacing a CAM with an efficient hash table lookup engine provides for rapid data search while overcoming the chip area and power consumption drawbacks associated with attempting to implement a large-scale CAM. It has been further recognized that employing an efficient hash lookup table in a packet-based communication node would improve the speed and efficiency of the node. For example, a chip-based packet node, such as an ASIC, may employ a combination of an on-chip cache memory and an off-chip memory to temporarily store packets while the packets await processing; and when such node needs to access a temporarily stored packet, an efficient hash table lookup engine will enable the node to rapidly determine whether the packet is stored in the on-chip cache memory or in the off-chip memory. In view of the desire for an efficient hash table lookup engine, the presently disclosed technology is provided. According to one aspect, a hash table system includes a plurality of hash tables, associated with respective hash functions, for storing key-value pairs;an overflow memory for storing key-value pairs moved from the hash tables due to collision; andan arbiter, which is a weighted round-robin arbiter, for arbitrating among commands including update commands for installing key-value pairs into the hash tables or uninstalling key-value pairs from the hash tables, match commands for matching keys to locations in the hash tables, and rehash commands for relocating key-value pairs from the overflow memory to the hash tables or relocating key-value pairs from one of the hash tables to another of the hash tables, wherein a weight applied to the update commands and the match commands is varied according to an occupancy level of the overflow memory, and wherein the weight is set to a value associated with an occupancy region of two or more occupancy regions of the overflow memory, the occupancy region determined according to the occupancy level, andwherein for each system clock cycle, the arbiter selects as a selected command one of an update command, a match command, or a rehash command. BRIEF DESCRIPTION OF THE DRAWINGS The accompanying drawings are not intended to be drawn to scale. Also, for purposes of clarity not every component may be labeled in every drawing. In the drawings: Fig. 1 is a high-level block diagram of a hash table system of an embodiment.Fig. 2 is a block diagram of a bucket used in the hash table system of Fig. 1 according to an embodiment.Fig. 3 is a block diagram of a hash table system of an embodiment.Fig. 4 is a block diagram of a background rehash engine of an embodiment. DETAILED DESCRIPTION Examples of systems and methods are described herein. It should be understood that the words "example," "exemplary" and "illustrative" are used herein to mean "serving as an example, instance, or illustration." Any embodiment or feature described herein as being an "example," "exemplary" or "illustration" is not necessarily to be construed as preferred or advantageous over other embodiments or features. In the following description, reference is made to the accompanying figures, which form a part thereof. In the figures, similar symbols typically identify similar components, unless context dictates otherwise. Other embodiments may be utilized, and other changes may be made, without departing from the scope of the subject matter presented herein. The example embodiments described herein are not meant to be limiting. It will be readily understood that the aspects of the present disclosure, as generally described herein, and illustrated in the figures, can be arranged, substituted, combined, separated, and designed in a wide variety of different configurations, all of which are explicitly contemplated herein. The present disclosure describes a hardware architecture of a high-performance and low-cost hash table lookup engine. The design has a high throughput. The install and lookup operations are completed within a fixed bounded number of cycles. Also, a dynam