Repository navigation
Performance
Performance is a complicated and nuanced topic, here are some considerations when tweaking LeakDB performance.
There are two main performance metrics we're concerned with while using the bloom filter:
- False-positive rate
- Execution time
The false-positive rate can be adjusted using --filter-size, which controls the size of the bloom filter in GBs and --filter-hashes, which controls the number of hash functions used by the filter. If you know the size of your dataset you can calculate these variables for a desired false-positive rate using a bloom filter calculator, but generally speaking the higher these two numbers the lower the false positive rate. However, increasing these values too high for a given dataset may increase execution time.
The bloom filter provides a --workers-bloom (or simply --workers depending on sub-command) option to adjust the number of worker threads that run in parallel during the bloom filter processes. However, the limiting factor is most likely your storage device not your CPU so increasing the number of workers is unlikely to yield better performance unless your storage device is out running your CPU. Additionally, increasing the number of workers also increases lock contention so there's a real chance that increasing this number my decrease execution time if you're not careful.
I've create a small gist where you can benchmark the false-positive rate of various bloom filter configurations. Note that what we're measuring here is the first collision, if you're data set is a few billion and you only have a collision every few hundred million you may only have a handful of false positives out of billions, which is likely an acceptable rate given the huge boost eliminating duplicates provides.
| Size (MBs) | Hashes | First Collision |
|---|---|---|
| 4096 | 1 | 38864 |
| 4096 | 2 | 1898627 |
| 4096 | 3 | 8984358 |
| 4096 | 4 | 24593095 |
| 4096 | 5 | 47794942 |
| 4096 | 6 | 55638144 |
| 4096 | 7 | 55638144 |
| 4096 | 8 | 65324131 |
| 4096 | 9 | 90920122 |
| 4096 | 10 | 95200145 |
| 4096 | 11 | 95200145 |
| 4096 | 12 | 113830445 |
| 8192 | 8 | 93486908 |
| 8192 | 9 | 118508088 |
| 8192 | 10 | 176112177 |
| 8192 | 11 | 181667654 |
| 8192 | 12 | 196639640 |
| 16384 | 8 | 238452839 |
| 16384 | 9 | 229788967 |
| 16384 | 10 | 352747219 |
| 16384 | 11 | 354910523 |
| 16384 | 12 | 382640039 |
| 16384 | 20 | 466046732 |
| 20480 | 14 | 491561566 |
| 30720 | 14 | 753850515 |
| 40960 | 14 | 837151349 |
Similar to the bloom filter, the indexer provides a --workers-index (or simply --workers depending on sub-command) option to adjust the number of worker threads that run in parallel during the index processes. While the limiting factor again will most likely be your storage device, there are no locks required for the indexer so increasing the number of --workers is more likely, though not always, to increase performance. The default number of workers is equal to the number of logical CPU cores available.
The largest impact to performance will be adjusting the --max-memory flag, which configures the maximum amount of the index file that is sorted at a time.
Important: Note that the --max-memory flag does not set the maximum memory usage of the processes, the process needs to store a lot of pointers into the index file so the actual total memory usage of the file will be much higher than the value you specify with this flag. For example, with the default value of 1024, the process will consume about ~14Gb of total RAM at its peak. Increasing this value too much my result in out-of-memory errors if the program attempts to allocate more memory than your hardware can provide. Increasing --max-memory will generally improve performance, but the impact may be minimal depending on your particular dataset and hardware.
LeakDB uses external quick sort to sort datasets larger than the amount of RAM your system has. This process works by splitting the dataset up into smaller "tapes" and sorting these tapes individually, then merging the sorted tapes to create a single sorted file. By increasing --max-memory you will be decreasing the number of tapes that need to be created and merged. However, it's important to note that quicksort's performance is affected by the data it is sorting. In datasets with a large number of identical values (such as a domain index) quicksort will perform poorly.