Maximizing Bloom Filter Efficiency on Hardware: Unleashing the Power of a Single Hash Function
In 1970, Howard Bloom presented space/time trade-offs for lookup algorithms in data structures based on hash coding with allowable errors. The author’s name has been linked to the presented algorithms ever since. The Bloom filter is an approximate membership query data structure used to determine whether an element is in a set of elements. The filter has two possible outcomes: 1) the element might be in the set, or 2) the element is not in the set. Although the first option can trigger false positives, the second option rules out false negatives.
A standard Bloom filter (SBF) that looks for an input x in a set S, consists of a bit vector of length m, and k hash functions, which are used to map the inputs to the bit vector. An example is shown in Fig. 1, where m is 14 and k is 3.
Initially, all the locations in the bit vector are set to zero. To update the input s1, it is mapped to the filter using three hash functions Hk1, Hk2, and Hk3. The hash values are used to index the bit vector. The bits in all the hash-indexed locations are set to 1 for each input. To query an element x, the hashing operation is performed similar to the update operation. If all the corresponding bits in the hash-indexed locations of the bit vector are set to 1, the SBF returns x ∈ S. Otherwise, x ∉ S is returned.
As stated above, a membership query can have a false positive result. This happens during hash collisions when all the hash-indexed locations of the non-existing queried element are already set to 1 due to the insertion of other elements.
The bottlenecks associated with Bloom filters
Bloom filters are very much efficient in tackling hash collisions by employing multiple independent hash functions. Nonetheless, a pertinent question remains: how efficient is the use of multiple independent hash functions?
Bloom filters encounter performance bottlenecks primarily due to the hash functions. As the number of hash functions increases, computational requirements increase, leading to a notable increase in the time taken for hash calculations and subsequently lowering the operating frequency. Implementing these hash functions in hardware poses an additional challenge, as each hash calculation requires a dedicated clock cycle, resulting in a latency of k clock cycles, where k represents the number of hash functions.
How to address the challenges associated with hash functions?
So, as the increased number of hash functions is the problem, can we just use a single hash function? Well, employing just one hash function can lead to a situation similar to a hash table. In such a scenario, it will have approximately 50% collisions if the number of elements to be added to the hash table is equal to the number of locations available in the table. Yet, the use of a perfect hash function, which ensures no collisions occur, would make a single hash function sufficient. Then, the question arises: Is it possible to use a perfect hash function?
Let’s take an example. Assume that the size of the element to be added to the filter is 96 bits. The allocated memory for the filter is 4096 bits, requiring the output size of the hash function to be 12 bits. However, collisions are inevitable when we compress a 96-bit input into a 12-bit hash digest. This is because we are trying to map 2⁹⁶ possibilities into a space of only 2¹². This is the reason why Bloom filters use multiple hash functions. By employing several hash functions, the chance of all of them producing collisions simultaneously decreases. This helps mitigate the impact of collisions, making the Bloom filter more effective in representing and querying data. Consequently, using a single hash function that generates a 12-bit digest for a 96-bit input is not feasible due to the significant loss of information and the high likelihood of collisions.
A Bloom filter with a single hash function!
How do we use a single hash function to implement a Bloom filter? A recent work[1] discusses a novel approach to implementing a Bloom filter using only a single hash function. The hash function used is Xoodoo-NC, which is the non-cryptographic version of the Xoodoo permutation. Xoodoo-NC takes a 96-bit input and can generate hash outputs that can be either 96 bits or multiples of 96 bits. Xoodoo-NC possesses excellent avalanche properties: near-perfect avalanche entropy, avalanche weight, and avalanche dependence. Thanks to these properties, the occurrence of collisions is nearly non-existent, as it perfectly maps a 96-bit input to a 96-bit (or multiples of 96) output. When there are no collisions, a single hash function proves sufficient.
Yet, there is another challenge to be addressed as the output hash size is 96-bit, and it requires a memory of size 2⁹⁶ bits to map the hash output to filter! In our example we stated earlier, we only have 4096 bits (2¹² bits) memory.
To address the issue of indexing 4096 locations in a Bloom filter using 96-bit hash output, the hash output is split into hash values of size 12 bits each. A 12-bit hash value can be used to index 4096 locations. Hence, the Bloom filter will have eight hash values, meaning k = 8. Instead of employing k distinct and independent hash functions, this approach utilizes a single hash function with a larger output size. Subsequently, the output of this hash function is partitioned into the k hash values necessary for the Bloom filter. An illustration is depitected in the figure below. This approach exhibits better collision resistance compared to the traditional approach that utilizes independent hash functions.
Detailed description and analysis of Bloom filter implementation using Xoodoo-NC can be found in the paper [1], and it can be downloaded here. Verilog code of a simple version of Xoodoo-NC can be found here.
References
[1] Sateesan, A., Vliegen, J., Daemen, J. and Mentens, N., 2022. Hardware-oriented optimization of Bloom filter algorithms and architectures for ultra-high-speed lookups in network applications. Microprocessors and Microsystems, 93, p.104619.
