maybe use cuckoo/bloom filter or fst+trie for seen_profiles

[ruslandoga]

nice and somewhat related (bloom):

• https://blog.medium.com/what-are-bloom-filters-1ec2a50c68ff#.xlkqtn1vy
• https://www.quora.com/What-are-the-best-applications-of-Bloom-filters
• https://freecontent.manning.com/all-about-bloom-filters/

nice and definitely related (cuckoo):

• https://bdupras.github.io/filter-tutorial/
• https://github.com/farhadi/cuckoo_filter

[ruslandoga]

When to delete a uuid from a filter? If deletions are scheduled in a job queue, there isn't much of a win over storing all seen uuids into seen_profiles table.

One way to do scheduled delete from filters is to create them per period, like each day -- new filter, and keep only the last 7, and when checking whether a uuid is seen, check filter from each period. Since filters can be small (just to be able to fit a period-worth uuids which is day's feed length * days in period), storage space and lookup speed (* # of periods) shouldn't be a problem.

Periods can also be made to be approximate, like we can always have 3 periods, and vary in-app how often they are rotated. A period can be a day, several days, a week, or even a month. On each rotation the last period is deleted, and a new filter is created in its place.

[ruslandoga]

Another approach is storing 'seens' into an FST, but it'd need to be periodically rebuilt from scratch (current period can be a trie, when current period ends, it can be rebuilt as fst). And scheduling deletins is a problem again.

• https://blog.burntsushi.net/transducers/

[ruslandoga]

How to filter 'seens' from feed queries in DB using this approach without copying all data into app? Not clear.

• https://www.postgresql.org/docs/13/bloom.html won't work