Looks like an interesting article, with complex problems and solutions. My problem is I have no idea what a "rotating bloom filter" would be used for in a real-world system.
accrual•1w ago
I also would like to know a use case, I know about bloom filters but not what makes a rotating one special. It sounds interesting but I wish the article lead with the purpose of the filter.
madduci•1w ago
It can be used for pseudo randomisation of data and a way to produce same values, given the same inputs, more close to what hashes with salt do.
FreakLegion•1w ago
It's a probabilistic cache. Standard Bloom filters can't add items indefinitely, and also can't evict old items to make room for new ones. Thus, rotating.
They should've just used a cuckoo filter.
drob518•1w ago
I’m not sure that problem 3 needs any solution at all, particularly a read-write lock. If a thread is updating the old set of bits when it’s time for a switch, just let it complete that write to the older set in parallel with the swap. Since the read path checks older sets of bits in any case, it really doesn’t matter if the bit is set in the latest bit-set or the older bit-set. Yes, it might age out slightly faster, but it would have done that anyway if the write had arrived a millisecond before the aging timer fired. If that bothers you, keep more old bit sets around and age them out faster.
lumimie5•1w ago
I think it's a problem because they snapshot the filter to avoid the atomic overhead, so you'd be writing to a stale copy, that will never be read. You could just keep the last 2 filters atomic instead, and skip the RWlock that way. Profiling might tell you which approach is better.
FloayYerBoat•1w ago
accrual•1w ago
madduci•1w ago
FreakLegion•1w ago
They should've just used a cuckoo filter.