News for hackers. Stuff that matters.
Re:100 more of those BITFIELDs by dvirsky on Friday February 26, 2016 @01:50PM (#11183187)
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.
Re:100 more of those BITFIELDs by connor4312 on Friday February 26, 2016 @02:01PM (#11183263)
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.

Re:100 more of those BITFIELDs by infogulch on Friday February 26, 2016 @03:00PM (#11183770)
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_ap... [1]: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

Re:100 more of those BITFIELDs by antirez on Friday February 26, 2016 @02:54PM (#11183712)
I wonder if you could use Redis hyperloglogs for this... You count IP ins in an HLL, COUNT IP out, and subtract.
Re:100 more of those BITFIELDs by dvirsky on Friday February 26, 2016 @04:39PM (#11184473)
sounds to me like it's more suitable for HLL than for blooms actually.