4 ms·

I'm quite excited for bitfields in Redis. We are going to need to implement some bloom filter-based data structures for one of our products in the near future.

I'm quite excited for bitfields in Redis. We are going to need to implement some bloom filter-based data structures for one of our products in the near future. Previously the best way to do this was to either keep a hash map or a binary k/v, both of which have substantial drawbacks (such as the need for locking). These bitfields, however, are a perfectly-timed ideal solution to the problem.

dvirsky 11y ago
You can implement bloom filters in redis >2.6 with SETBIT And GETBIT. But I'm guessing this is not your case exactly? I'm curious what exactly you're trying to model.
- connor4312 11y ago
  We want to count the number of users, including guests, who are currently viewing a resource. To count guests, we plan to count unique IPs, so each IP should be counted at most once even if it connects to several different servers as a result of load balancing. The approach we're moving towards is an augmented bloom filter where each "bit" is actually an unsigned integer counting the number of items hashed to the position, allowing us to add and remove IPs to the filter as users come and go (just rehashing and "subtracting" the IP when it leaves). This lets us ensure that IPs are not counted more than once. SETBIT and GETBIT would work with a normal filter, but they can't increment multiple bits, so we'd end up needing to lock.
  - antirez 11y ago
    I wonder if you could use Redis hyperloglogs for this... You count IP ins in an HLL, COUNT IP out, and subtract.
    - dvirsky 11y ago
      sounds to me like it's more suitable for HLL than for blooms actually.
  - infogulch 11y ago
    Ah yes, a counting filter. [0] How do you plan on tackling rare overflow? Have you looked at Cuckoo Filter [1]? Same abilities as a counting bloom filter, but has some advantages like reducing false positives while using even less memory and requiring less processing. [0]: https://en.wikipedia.org/wiki/Bloom_filter#Extensions_and_applications https://en.wikipedia.org/wiki/Bloom_filter#Extensions_and_ap... [1]: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

dvirsky 11y ago

You can implement bloom filters in redis >2.6 with SETBIT And GETBIT. But I'm guessing this is not your case exactly? I'm curious what exactly you're trying to model.

connor4312 11y ago
We want to count the number of users, including guests, who are currently viewing a resource. To count guests, we plan to count unique IPs, so each IP should be counted at most once even if it connects to several different servers as a result of load balancing. The approach we're moving towards is an augmented bloom filter where each "bit" is actually an unsigned integer counting the number of items hashed to the position, allowing us to add and remove IPs to the filter as users come and go (just rehashing and "subtracting" the IP when it leaves). This lets us ensure that IPs are not counted more than once. SETBIT and GETBIT would work with a normal filter, but they can't increment multiple bits, so we'd end up needing to lock.
- antirez 11y ago
  I wonder if you could use Redis hyperloglogs for this... You count IP ins in an HLL, COUNT IP out, and subtract.
  - dvirsky 11y ago
    sounds to me like it's more suitable for HLL than for blooms actually.
- infogulch 11y ago
  Ah yes, a counting filter. [0] How do you plan on tackling rare overflow? Have you looked at Cuckoo Filter [1]? Same abilities as a counting bloom filter, but has some advantages like reducing false positives while using even less memory and requiring less processing. [0]: https://en.wikipedia.org/wiki/Bloom_filter#Extensions_and_applications https://en.wikipedia.org/wiki/Bloom_filter#Extensions_and_ap... [1]: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf