Bloom filter is slower than Lua

[erikdubbelboer]

A long time ago I have written a scaling bloom filter for redis using Lua: erikdubbelboer/redis-lua-scaling-bloom-filter

When doing some benchmarks I was quite surprised that the Lua version always a lot less memory and can be quite a bit faster in certain cases. It seem like only small filters are faster in redablooms. I'm afraid I don't have the time to dive in the code and figure out why exactly.

$ redis-benchmark -r 100000000 -n 1000000 -c 20 evalsha `redis-cli --eval add.lua | sed 's/.*f_\([0-9a-z]\{40\}\).*/\1/'` 0 test 10000 0.01 __rand_int__
====== evalsha ab31647b3931a68b3b93a7354a297ed273349d39 0 test 10000 0.01 __rand_int__ ======
  1000000 requests completed in 31.81 seconds
  20 parallel clients
  3 bytes payload
  keep alive: 1

99.46% <= 1 milliseconds
100.00% <= 2 milliseconds
100.00% <= 2 milliseconds
31440.61 requests per second

$ redis-cli info | grep human
used_memory_human:5.56M
used_memory_rss_human:7.11M
used_memory_peak_human:6.48M
total_system_memory_human:16.00G
used_memory_lua_human:36.00K
maxmemory_human:0B

$ # reset redis

$ redis-cli sbf.init test 10000 0.01
OK
$ redis-benchmark -r 100000000 -n 1000000 -c 20 sbf.add test __rand_int__ \+
====== sbf.add test __rand_int__ + ======
  1000000 requests completed in 44.03 seconds
  20 parallel clients
  3 bytes payload
  keep alive: 1

62.51% <= 1 milliseconds
99.23% <= 2 milliseconds
99.95% <= 3 milliseconds
99.99% <= 4 milliseconds
99.99% <= 5 milliseconds
100.00% <= 6 milliseconds
100.00% <= 7 milliseconds
100.00% <= 7 milliseconds
22710.76 requests per second

$ redis-cli info | grep human
used_memory_human:41.29M
used_memory_rss_human:43.08M
used_memory_peak_human:42.20M
total_system_memory_human:16.00G
used_memory_lua_human:37.00K
maxmemory_human:0B

[itamarhaber]

Hi Eric and thanks for reporting this - I'm familiar with your implementation in Lua and it is a pleasure to meet here :)

This "shouldn't happen" but I'll need a few hours to dig into this. Keeping this open until then.

[dvirsky]

From the Makefile:

CFLAGS = -I$(RM_INCLUDE_DIR) -g -fPIC -lc -lm -O0 -std=gnu99 

I'm guessing changing -O0 to -O2 or 3 will improve things a bit.

[erikdubbelboer]

I'm guessing there is a miscalculation in the precision or the filters code somewhere. For the above test this module uses 101 layers while my Lua code only uses 8 or 9 layers.

-O3 only made a small difference:

$ redis-cli sbf.init test 10000 0.01
OK
$ redis-benchmark -r 100000000 -n 1000000 -c 20 sbf.add test __rand_int__ \+
====== sbf.add test __rand_int__ + ======
  1000000 requests completed in 37.58 seconds
  20 parallel clients
  3 bytes payload
  keep alive: 1

75.45% <= 1 milliseconds
99.92% <= 2 milliseconds
99.99% <= 3 milliseconds
100.00% <= 4 milliseconds
100.00% <= 4 milliseconds
26608.48 requests per second

$ redis-cli info | grep human
used_memory_human:41.29M
used_memory_rss_human:43.48M
used_memory_peak_human:42.20M
total_system_memory_human:16.00G
used_memory_lua_human:37.00K
maxmemory_human:0B

[avram]

@itamarhaber Has your team had a chance to follow up on the performance here? We're looking at moving some workloads to in-Redis bloom filters.