twitter / pelikan

Pelikan is Twitter's unified cache backend
Apache License 2.0
1.94k stars 176 forks source link

Add a bloom filter storage module #460

Closed swlynch99 closed 2 years ago

swlynch99 commented 2 years ago

This PR introduces a bloom filter storage module. At the moment it only contains the bloom filter data structure, docs, benchmarks, and tests. In future PRs I will add a protocol that makes use of the bloom filter.

Performance

I don't think I could get this to be appreciably faster if I tried. I have added some criterion benchmarks under src/storage/bloom/benches. Here are the results:

unit                    time:   [116.81 ns 118.67 ns 120.47 ns]

u64                     time:   [130.20 ns 131.42 ns 132.77 ns]

small_slice             time:   [251.02 ns 252.92 ns 254.75 ns]

large_slice             time:   [21.259 µs 21.306 µs 21.352 µs]