3 ms·
Bloom filters are unsuitable for implementing a cache. For one, they provide membership queries, not lookups. In the article, the problem was reduced to members
by lorenzhs 11y ago
Bloom filters are unsuitable for implementing a cache. For one, they provide membership queries, not lookups. In the article, the problem was reduced to membership queries so it would not be an issue for this specific setting, but that limits its usability in practice.
Second, Bloom filters have false positives. In the use case of cache lookups, you'd usually be fine with false negatives (querying the database even if we didn't really have to, i.e. a bit more work) but not false positives (what do you do then?).
Third, Bloom filters don't support deletion unless you use counting bloom filters, which would reduce the space advantage dramatically. Normally, your cache will be of limited size, so you will need deletion for eviction.
Bloom filters are not the right data structure for the job.
- tantalor 11y agoDon't you have that backwards? The question bloom filter solves is, "Does my database possibly have a value for this key?" If a cache gives a false negative (bloom filter cannot) then you immediately return a null response without querying the database, but the database does have the key; this is incorrect behavior. If a cache gives a false positive (bloom filter can) then you query the database and get a null response since the database does not have the key; this is correct behavior, although it has a performance penalty.
- lorenzhs 11y ago> Don't you have that backwards? The question bloom filter solves is, "Does my database possibly have a value for this key?" No, since the cache is there to avoid having to query the database. Querying the database happens on a cache miss, and if there is no data there, then that's the answer. It seems that we are talking about different applications.