Bloom filters are an essential component of an LSM-based database engine like MyRocks. This post will illustrate through a simple example how bloom filters work in MyRocks.
Why?
With MyRocks/RocksDB, data is stored in a set of large SST files. When MyRocks needs to find the value associated with a given key, it uses a bloom filter to guess if the key could potentially be in an SST file.
How?
A bloom filter is a space-efficient way of storing information about a list of keys. At its base, there is a bitmap and a hash function. The hash value of the keys stored in an SST is computed, and the results are used to set some bits to “1” in the bitmap. When you want to know if a key is present or not in the list, you run it through the hash function and check if the corresponding bits in the bitmap are “1” or “0”. If one of the bits is “0”, you know for sure the key is not in the list. If all the bits are “1”, the value may be present. The probability of a false positive depends only on a few factors:
- Size of the bitmap
- Number of keys in the list
- Number of bits set to “1” for each key value
An example
Let’s assume we are creating a list of names and want a bloom filter on that list. We’ll use an 8 bytes bloom filter (64 bits), and we’ll set two bits according to this function:
mysql> set @md5value=md5('Yves');select mod(conv(mid(@md5value,1,8),16,10),32) b1, mod(conv(mid(@md5value,9,8),16,10),32)+32 b2;
Query OK, 0 rows affected (0.00 sec)
+------+------+
| b1 | b2 |
+------+------+
| 15 | 39 |
+------+------+
1 row in set (0.00 sec)
So the value ‘Yves’ sets the bits 15 and 39 to ‘1’.
Now, if I add 10 names (taken from the Percona slack channel “architecture_projects”) we have:
- Alexey: 29 53
- Alick: 8 49
- Bennie: 31 63
- Brenda: 20 54
- Brett: 12 61
- Carlos: 3 46
- Corrado: 27 34
- David: 15 57
- Deb: 13 38
- Eliana: 11 39
The bitmap now looks like:
0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0 1
Now, if I want to use the bitmap to “guess” if “Bennie” is in the list, that will work just fine, bits 31 and 63 are “1”. But… “Yves” is not in the list even though bits 15 (from David) and 39 (from Eliana) are set to “1”. A query for “Yves” would be a false positive.
On the other hand, let’s consider “Francisco” for which the bits are 27 and 60. Bit 27 is set to “1” by the “Corrado” value, but bit 60 is “0”. We thus know for sure that “Francisco” is not in the list.
Tuning
In terms of tuning, two parameters can be tuned, the size of the bitmap and the number of bits set by every value. The bitmap size must be large enough so that the proportion of bits set to “1” is not overwhelming. In the above example, if you add all the first names of the people at Percona you’ll end up with only “1”. That would be obviously useless. To avoid this issue, we could instead use a 1 GB bitmap. The number of false positives would be low, but 1GB is a lot of memory. In most cases a bitmap of a few hundred bytes is sufficient.
With MyRocks, you can control the size of the bloom filter bitmap with the column family parameter memtable_prefix_bloom_size_ratio. For good performance, the filter blocks are cached in the RocksDB block cache and normally stay there since they are accessed frequently.
The filter_policy variable controls the number of bits per key in the column family settings. By default, 10 bits are used per key which yields less than 1% of false positives.
Conclusion
I hope that this post has provided you with a basic understanding of bloom filters and how they are implemented in MyRocks. LSM storage engines like MyRocks are very different from the more common B-Tree-based storage engines like InnoDB. Bloom filter is an important feature improving performance of LSM storage engines. A good understanding of how bloom filters work can only lead to improved database performance.
Percona Distribution for MySQL is the most complete, stable, scalable, and secure open-source MySQL solution available, delivering enterprise-grade database environments for your most critical business applications… and it’s free to use!
I wrote this post on MyRocks because I believe it is the most interesting new MySQL storage engine to have appeared over the last few years. Although MyRocks is very efficient for writes, I chose a more generic workload that will provide a different MyRocks use case.
Raspberry PI is a small single-board computer (SBCs) developed by the Raspberry Pi Foundation in association with Broadcom. This tiny computer is extremely popular and widely used in many areas. Thanks to its size, low cost, and low energy requirements, it can be used to collect data in remote locations or from sensor devices. We often need to be able to store large amounts of data efficiently on these devices.
As database footprints continue to explode, many companies are looking for ways to deal with such rapid growth. One approach is to refactor traditional relational databases to fit into a NoSQL engine, where horizontal scalability is easier. However, in many cases, this is in no way a trivial undertaking.
Percona Technical Account Managers get the privilege of working with some of our largest enterprise clients day in and day out. As such, we get to really focus on how to best leverage our technology to generate measurable benefits for our users. While it is fun to “nerd out” and always strive to use the latest and greatest, we need to stay focused on demonstrating business value and a genuine need. Over the past few months, I’ve been working with one of my larger clients, 
In my webinar 
RocksDB engine—and it’s MySQL implementation MyRocks—is a very good alternative engine for MySQL. It has proven to be very efficient and stable for many workloads, including those of large scale. However, it is still a relative newborn in the MySQL ecosystem, and has only a small fraction of the adoption rate of InnoDB. That means it is not so well tested at all possible edge cases, and may have many unreported bugs. One known bug is discussed here: if you are a MyRocks user, it’s important that you are aware of the possibility of lost data in the specific circumstances described below.
