Efficient hash table lookup

Patent metadata

Field	Value
Publication number	US-12475167-B2
Application number	US-202418423766-A
Country	US
Kind code	B2
Filing date	Jan 26, 2024
Priority date	Jun 6, 2022
Publication date	Nov 18, 2025
Grant date	Nov 18, 2025

Abstract

A hash table system, including 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; and an arbiter for arbitrating among commands including update commands, match commands, and rehash commands, 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, and wherein the hash table system completes execution of each selected command within a bounded number of system clock cycles.

First claim

The invention claimed is:

1 . A hash table system, comprising a plurality of hash tables, associated with respective hash functions, for storing key-value pairs, wherein each hash table comprises a plurality of buckets, and each bucket comprises a plurality of cells, wherein each cell is operable to store a key-value pair, wherein each key hashes to one of the buckets in each hash table, and wherein when the system performs an install operation for a key-value pair, a bucket in each hash table is determined for the key-value pair to be stored by hashing the key with the respective hash functions, and the key-value pair is stored in a hash-table for which the determined bucket is not full,
wherein when all of the buckets determined for a key-value pair to be stored are full, a key-value pair previously stored in one of the determined buckets is evicted and stored in an overflow memory, and the key-value pair to be stored is stored in the bucket from which the key-value pair previously stored is evicted.

2 . The system according to claim 1 , wherein the overflow memory is configured so that a location of a key-value pair stored in the overflow memory is determined by searching for the key of the key-value pair.

3 . The system according to claim 2 , wherein the overflow memory comprises a content addressable memory for storing keys of key-value pairs, and another memory for storing values of the key-value pairs.

4 . The system according to claim 1 , further comprising:
the overflow memory for storing key-value pairs moved from the hash tables due to collision; and an 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 for each system clock cycle, the arbiter selects as a selected command one of an update command, a match command, or a rehash command, and wherein the hash table system completes execution of each selected command within a bounded number of system clock cycles, wherein the arbiter is a weighted round-robin arbiter.

5 . The system according to claim 4 , wherein a weight applied to commands that are not rehash commands is varied according to an occupancy level of the overflow memory.

6 . The system according to claim 5 , wherein the weight applied to commands that are not rehash commands is set to a first value when the occupancy level of the overflow memory is less than a first threshold, is set to a second value greater than the first value when the occupancy level of the overflow memory is greater than the first threshold and less than a second threshold, and is set to a third value greater than the second value when the occupancy level of the overflow memory is greater than the second threshold.

7 . The system according to claim 6 , wherein the first threshold is an overflow memory high occupied threshold, and the second threshold is an overflow memory almost full threshold.

8 . The system according to claim 1 , further comprising:
the overflow memory for storing key-value pairs moved from the hash tables due to collision; and an 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 for each system clock cycle, the arbiter selects as a selected command one of an update command, a match command, or a rehash command, wherein the hash table system completes execution of each selected command within a bounded number of system clock cycles, and wherein the rehash commands comprise two types of rehash commands, a candidate generation type of rehash command for selecting a key-value pair 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.

9 . The system according to claim 8 , wherein move type rehash commands are prioritized over candidate generation type rehash commands.

10 . The system according to claim 8 , wherein when a plurality of keys corresponding to candidate key-value pairs 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 in the overflow memory over candidate keys corresponding key-value pairs in the hash tables.

11 . The system according to claim 8 , wherein when a plurality of keys corresponding to candidate key-value pairs 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 and fails, the candidate key-value pair is moved into a hash table location occupied by a selected key-value pair, the selected key-value pair is moved into the overflow memory, and the key corresponding to the selected key-value pair is designated as a looped-back key, and is stored in the one or more candidate memories.

12 . The system according to claim 11 , wherein when a plurality of keys corresponding to candidate key-value pairs 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.

Assignees

• Google Llc

Inventors

• Jiang Weiwei
• Vaduvatha Srinivas
• Chandra Prashant R
• Zheng Jiazhen
• Walsh Hugh Mcevoy
• Wang Weihuang
• Agarwal Abhishek

Classifications

• G06F3/0673

  Single storage device · CPC title

• G06F3/0659

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

• G06F3/0613

  in relation to throughput · CPC title

• G06F16/9017

  using directory or table look-up (use of a directory or look-up table in file systems G06F16/13) · CPC title

• G06F16/2255

  Hash tables · CPC title