Alexander Eichhorn

Revisiting Bloom Filter Efficiency in LSM Trees - thoughts from some recent readings .. Almost all LSM based storage structures use bloom filters in front of their memtable structures to reduce IO overhead at least for the target keys not present in the underlying secondary storage. This decision to use bloom filters is based on the fact that accessing data on secondary storage, e.g., hard disk drives (HDD) or solid-state drives (SSD), is several orders of magnitude more expensive than probing the filter in memory. Overall, BFs reduce the number of disk accesses and the overall query latency at the price of additional memory footprint and CPU computation. The question is - is this scenario likely to change in the context of newer and faster storage devices ? And are bloom filters in the current incarnation the be-all and end-all to improving performance in LSM based storage ? Let’s take a look .. Faster storage devices like SSDs and non-volatile memories (NVMs) - These can turn out to be the game changer. Quoting from this paper [1] by Zhu et. al. - “Taking into account that current SSD devices have several orders of magnitude lower access latency than disk, and that future SSDs and NVMs are bound to be faster, hashing latency is on its way to becoming comparable with data access latency. For example, accessing a 4KB data page on our off-the-shelf SSD needs 113μs, while the cost of hashing a 1KB-key using MurmurHash64 (...) is 235 ns, making storage about 480× more expensive than hashing. However, accessing a data page of our PCIe SSD device takes 10 μs [31] (7μs when bypass- ing the file system using Intel’s SPDK [42]), reducing this gap to 42x (30x without file system). In addition, future NVM devices are expected to offer access latency as low as ∼250 ns, being only 1.6x slower than DRAM [..], hence, making storage access comparable to hashing. Note that when data is cached in main memory, our experiments show that a single hash function calculation is ∼1.47x more expensive than accessing a memory page, thereby, making the use of a BF detrimental.” And this LSM hashing overhead gets further magnified as each lookup in the tree needs multiple bloom filter queries, at least one per level in the current implementations. Such repeated hash calculations turn querying over fast storage (or cached data) into a CPU-intensive operation. In order to address this issue we are seeing quite a few improvements and optimizations being suggested in various research papers and some of them have possibly been implemented in current LSM based stores as well (e.g. RocksDB). Here are a few of them - 1. Reducing the computational complexity of hashing. ​​Bloom filters are based on a number of hash functions and for each LSM tree we need to have multiple bloom filters (as noted above). This involves generating a number of hash functions, which, in the context of bloom filters, works but is computationally expensive. One way to reduce this complexity is to use the combinatorial approach. In this approach the bloom filter indexes are computed using a single hash function, followed by much cheaper bitwise operations (rotations and modulo) to generate the remaining indexes to be probed. This was first suggested in a paper [2] by Kirsch and Mitzenmacher. They suggest an approach that uses the combinatorial property of hash functions, where, given 2 hash functions h1(x) and h2(x), additional hash functions can be generated using a linear combination of them. This process yields the necessary number of hash functions in a bloom filter without the overhead of calling the hash calculation multiple times. However, Jianyuan Lu et. al. notes in their paper [3] that this technique cannot guarantee the independence of the synthetic hash functions, the false positive ratio in practice could be much higher than the theoretical expectation. They suggest an alternative approach which they call One-Hashing Bloom Filter (OHBF), which can be used to generate hash functions for bloom filters with low computational complexity. 2. Improving cache efficiency of bloom filters. A Bloom filter using k hash functions performs the same number of memory accesses. In the worst case, k cache misses can happen in one element query. The idea is to improve the cache efficiency by cutting the Bloom filter into blocks, each of which fits into one cache line. This paper [4] by Putze, Sanders and Singler presents a family of cache efficient bloom filters that offer more flexible trade-offs between false positive rate, space-efficiency, cache-efficiency, hash-efficiency, and computational effort. The bloom filter implementation in RocksDB uses this strategy (github.com/rockset/rocksdb-c…). 3. Hash Sharing. Once the CPU computational complexity of hash computation is reduced as in 1 above, this efficiency can further be extended to implement sharing hash computations across multiple LSM levels and across a series of smaller bloom filters that forms a single logical bloom filter. [1] has more details. [1] Reducing Bloom Filter CPU Overhead in LSM-Trees on Modern Storage Devices by Zhu et. al. - dl.acm.org/doi/10.1145/34659… [2] Building a Better Bloom Filter by Adam Kirsch and Michael Mitzenmacher - eecs.harvard.edu/~michaelm/p… [3] Low Computational Cost Bloom Filters by Jianyuan Lu et. al. - yangtonghome.github.io/uploa… [4] Cache- Hash- and Space- Efficient Bloom Filters by Felix Putze, Peter Sanders and Johannes Singler - algo2.iti.kit.edu/documents/… BTW in case anyone wants to take a look at how a production ready scalable bloom filter looks like, take a look at the one implemented as part of RocksDB (github.com/rockset/rocksdb-c…) and the associated wiki page (github.com/facebook/rocksdb/…)