3 ms·
This is a neat idea. However, the Redis backend seems rather pointless. If I'm understanding the code correctly, each bit of the filter is implemented as an ite
by MichaelGG 15y ago
This is a neat idea. However, the Redis backend seems rather pointless. If I'm understanding the code correctly, each bit of the filter is implemented as an item in Redis. From the comments[1] the overhead is ~130 bytes. So each bit ends up needing 1000 bits? At that point, it'd be even be more efficient to just use a hashtable with the SHA256 hash of the item as the key and storing a count+expiry time...
[1]: In the comments: "The simple backend I added treats each key as an individual bucket, and based on my rough testing, Redis added about ~130 bytes of overhead per key - which, of course, is a huge difference compared to the bit vector."
- slig 15y agoNowadays one can use GETBIT[1] and SETBIT[2] to do it efficiently. [1] http://redis.io/commands/getbit http://redis.io/commands/getbit [2] http://redis.io/commands/setbit http://redis.io/commands/setbit
- MichaelGG 15y agoExcept the point in this case was to use Redis's built-in TTL system, which won't work if it's a single key.
- igrigorik 15y agoNew version of bloomfilter.rb uses SETBIT/GETBIT: https://github.com/igrigorik/bloomfilter-rb/blob/master/lib/bloomfilter/redis.rb https://github.com/igrigorik/bloomfilter-rb/blob/master/lib/... The "bit" per key was prior to setbit/getbit functionality. The new implementation is, in fact, very efficient.
- MichaelGG 15y agoBut not for the one that supports expiry: https://github.com/igrigorik/bloomfilter-rb/blob/master/lib/bloomfilter/counting_redis.rb#L55 https://github.com/igrigorik/bloomfilter-rb/blob/master/lib/... As the point is to use Redis's expiration feature, which obviously does not apply to individual bits.