Bloom filters are great, I wish more people knew about them. The most important part about a bloom filter:
They will never have a false negative (and only sometimes a false positive).
We used this to vastly improve render times for comments pages on reddit. We used two tricks. The first was to store the time of your last vote as a first class property on your user object. If you loaded a comments page for a link that was submitted after your last vote, we knew that you couldn't have voted on any of those comments.
But if you had voted afterwards, we had to look up every single comment on the page to see if you had voted on it (we couldn't only do the comments made before your last vote because we didn't know the creation time until after we looked up the comment, and it was faster to just look up the vote).
But with a bloom filter, we could very quickly look up all the comments and get back a list of all the ones you voted on (with a couple of false positives in there). Then we could go to the cache and see if your actual vote was there
(and if it was an upvote or a downvote). It was only after a failed cache hit did we have to actually go to the database.
But that bloom filter saved us from doing sometimes 1000s of cache lookups.
That's wonderful. Can you help me understand why every single button click on Reddit has an 800ms user visible latency gap? Reddit has always been this way, ever since its very beginning. Its latency has always been so slow compared to Hacker News. Why can't Reddit go snappy like HN? Is Python just really really slow compared to LISP? Why didn't your bloom filter improve user visible latency?
I can't tell if you're trolling or serious. If you're serious, I think the problem may be on your end, because I don't see that latency, and when I worked there, we didn't see that latency either.
My average latency on reddit is about 150ms, most of that network transit time. Some calls are slow, yes, but on average site wide when I worked there is was about 300ms (yes we measured it).
> Is Python just really really slow compared to LISP?
Now I'm almost certain you're trolling. Reddit was originally written in LISP. It was rewritten to Python for a massive speedup. Then we rewrote parts of it in C for another speedup. And now I'm pretty sure they have Rust and Golang too.
I am serious. If you're not logged in then reddit pages will take 150ms to respond if you exclude the snooserv ?rdt=xxxx redirect (which makes it take 200ms total).
master jart@luna:~/cosmo$ time curl --tcp-fastopen -L 'https://www.reddit.com/r/torties/comments/1hldi83/i_adopted_two_girls/' 2>/dev/null | head -c1 >/dev/null
real 0m0.203s
user 0m0.016s
sys 0m0.006s
But if you're logged in as "jart" and use that chrome inspect feature to "copy as curl command" and run it on the shell, then the above URL takes 800ms to respond. Pretty much every page on Reddit takes 800ms+ to send back the first byte of content. Yes I use old reddit mode. I imagine the same problem afflicts all your long time loyal fans who uses Reddit while logged in. FWIW my ping to reddit.com is 4.5ms.
You could contact them but honestly that probably wouldn't work very well. Things that might help: switch your settings from old reddit to new reddit, use new reddit to load a few pages, and then switch back. Also try using "newest" reddit at https://sh.reddit.com.
Did you maintain a single bloom filter for each user listing the comment IDs they had voted on across the whole site, or was it one bloom filter per user per thread?
I honestly don't remember for sure, but I believe it was one row per comment with a list of everyone who voted on it. So you could quickly get the answer to "did user X vote on comment Y?"
And of course the answer from a bloom filter was either "no" or "probably yes?", which was good enough to then do an actual lookup of that person's vote on that comment.
They will never have a false negative (and only sometimes a false positive).
We used this to vastly improve render times for comments pages on reddit. We used two tricks. The first was to store the time of your last vote as a first class property on your user object. If you loaded a comments page for a link that was submitted after your last vote, we knew that you couldn't have voted on any of those comments.
But if you had voted afterwards, we had to look up every single comment on the page to see if you had voted on it (we couldn't only do the comments made before your last vote because we didn't know the creation time until after we looked up the comment, and it was faster to just look up the vote).
But with a bloom filter, we could very quickly look up all the comments and get back a list of all the ones you voted on (with a couple of false positives in there). Then we could go to the cache and see if your actual vote was there (and if it was an upvote or a downvote). It was only after a failed cache hit did we have to actually go to the database.
But that bloom filter saved us from doing sometimes 1000s of cache lookups.