Engineering stories behind the Medium Daily Digest Algorithm: Part 2

How we made our filtering 10x cheaper by removing our Bloom Filters

Bloom Filters are great tools to make fast and cheap filtering. They also come with plenty of problems and can easily get expensive and cumbersome. We switched to user-based direct database queries, which made our filtering cheaper and easy to maintain. Here’s the full breakdown of that migration.

Intro: This is a 4-part series breaking down improvements to the algorithm behind the Medium’s Daily Digest over the past year. When we started this work, the Digest was suboptimal — and since it’s a huge distribution surface, reaching millions of readers every day, we started working on incremental improvements.

By the end of these projects, the digest was 10% more likely to convert users to paying members, less expensive to run, more flexible and easier to maintain and it’s now providing higher quality recommendations for all our users, including our “power readers”.

This is told through the lens of our engineering team tackling a series of challenges one by one. Medium has a small team but we operate on a big scale. We’re working our way through some technical debt and at the same time, striving to provide the best experience for our readers. This is the source of many interesting challenges.

I hope this series helps you understand how the recommendations algorithm work and can help others who are facing similar technical challenges.

This is probably the most technical story in the series, but I will keep it as simple as possible and hopefully this is interesting for non-technical readers too.

Some Concepts

Here’s a little cheat sheet with some concepts you may need to follow along with this story

Bloom Filters at Medium

A lot of the filters I mention in this series are backed by Bloom Filters (I’ve described some of those filtering rules in Part 1 if you haven’t read it already). We use Bloom filters to remove stories we think won’t interest readers from their feeds and other recommendations:

For example:

• our “muted” filter removes all stories from writers that you have muted
• our “read” filter removes all stories that you have already read
• our “presentation” filter removes all stories that have already been presented to you 3 times or more

These all rely on Bloom Filters

So what’s a Bloom Filter?

I asked Claude to summarize Bloom filters in a really simple way and it went with a funny analogy I’m going to try here.

A Bloom filter is like a super-efficient bouncer at a club who has a really good memory but isn’t perfect. It lets you do two things:

1. let someone into the club
   → in code that would be an add(string) function
2. lets you ask if someone is in the club. There are two possible answers to this:
   → “yes, probably”
   → “no, definitely not”
   → in code that would be a check(string) --> bool function

That doesn’t sound super useful like that but we’ll see next that it’s actually kinda well suited for recommendation systems.

At Medium we’re using it to store information such as “user a read story x” or “user a muted user b”. We add those to the “club” as strings, like read|user_x|story_y . Later on, when we want to know if user x has already read story y, we just ask our “bouncer”: is read|user_x|story_y in the club?

The scale of the filtering

What’s nice with Bloom filters is that they are able to store the information very efficiently and they are able to handle big amounts of requests per second. We don’t really need to know more about the inner workings of Bloom filters for this series but you can read more about it here (and it has some Excalidraw schemas too 🤌).

When we’re building a feed for a user (the digest for example), we’re sometimes sourcing up to 5000 stories as the initial “shortlist” of stories. This shortlist goes through many different steps and when we’re done, there’s only a handful of stories, ready to be sent in your digest 🙌

Ideally we should filter out stories as early as possible in the process. If we take the filters I’ve listed above, we’re asking ourselves 3 questions for every story in the short list:

• did the user read this story already?
• is the writer of the story muted by the user?
• was the user presented this story more than 3 times already?

So that can add up to 15k questions in total for a single user feed, and we process thousands of feeds per second. So that’s more than 15M questions per second. You can see how that can get out of hand and become expensive very quickly, we’re going to need some solid infrastructure to handle this.

Fortunately our Bloom filter “bouncer” is able to answer an insane amount of questions per second for pretty cheap, which is exactly what we’re looking for.

Bloom Filter downsides

The biggest downside for us is that even though the Bloom filters are super memory efficient, we overused them so much by adding literally billions of items that they started getting really really big and expensive. Like I mentioned before, there are only two operations you can do on a Bloom filter: add or check. There’s no way to delete any data from the filter (remove people from the club, if we stick with the bouncer analogy). And so the club can only grow in size, there’s no way to perform routines cleanups for information that we don’t need anymore.

The only way to reduce the size of the club is to start a new club with a new bouncer and then retire the old club and bouncer.

There are also a few more downsides:

• you can’t list the items that are stored (you can’t get a list of people who are in the club…). So we can’t go and see what’s stored for a given user, this makes it really hard to debug issues with the filters
• you can’t remove anyone from the club, which means that you can’t change your mind. For example if a user “unmutes” a writer, there’s no way to reflect that in the Bloom filter. That writer will be muted forever for that user. Yes, that’s very janky.
• this is derived data. For example the user “mutes” are stored in a proper database, and anytime there is a mute action we need to forward that information to the bloom filter. This is inconvenient and introduces data drift issue and more complexity overall.

All in all, there were too many downsides so we decided to explore a different approach.

Replacing the “Muted Filter”

When we build the feed for a given user, it happens in real time. It can be when you load the Medium homepage, or when we trigger the daily digest generation. We’re typically in the following situation:

• we have a shortlist of 1000 stories
• we want to filter out the stories from writers that are muted by the user

There are two ways to go about this:

A. perform a lookup in the database table that keeps track of muted writers for the 1000 (userID, writerID) pairs and check the mutedAt attribute

This is extremely expensive which is why we have to introduce a Bloom filter, where lookups are faster and cheaper

B. or fetch ALL of the muted writers for the current user and then cross-reference that with your shortlist of stories

Approach B has a massive advantage: most users do not mute anyone. So on average, we’re reading a very small amount of data from the database. If we were to do that with dynamoDB, B is a Query that retrieves on average less than 1 item from the DB for each feed. This is very cheap and fast. For “power muters” — users who mute massive amounts of writers, in the thousands — we can still handle this in real time although with higher latencies.

So this approach immediately obliterates the need for a Bloom filter. We have a fast, cheap, reliable way to filter out muted writers. We can also use our “ground truth” database directly, no need for derived data with all the headaches this involves.

So that’s one less Bloom filter! Let’s move on to the next one.

Replacing the “Presentation Filter”

The question becomes a bit trickier when we look at the “presentation” filter. We’re typically in a situation where:

• we have a shortlist of 1000 stories
• we need to remove all the stories that were presented to the user in a feed (in the past) 3 times or more

We’re currently doing that filtering using a Bloom filter. But you might wonder how we can even do that with Bloom filters. Remember there’s only two operations you can do with a bloom filter:

• add someone to the club
• ask if someone is in the club

Bloom filters were not built to maintain counters, only true / false information. So we have to hack our way around it by layering them. In terms of clubs and bouncers, it’s like we have a big festival with a bouncer. Inside the festival there’s a private club with another bouncer. And inside that private club there’s a VIP zone with another bouncer… Ultimately we only want to know if someone is inside the VIP zone, so we only need to ask the VIP bouncer. But we still need the two other bouncers to keep track of who’s eligible to get in the VIP zone…

Going back to Bloom filters: we use 3 layers of Bloom filters, on top of each other, with each one encoding the information “post was presented to user x times”

From the recommendations algorithm’s perspective it’s fairly simple, we just lookup the (user, post) pairs in the Bloom filter that encodes the “3” value of the counter (we just ask the VIP bouncer)

NB: that’s the implementation in place at Medium. I don’t know what went into consideration when building it this way. But FIY there are other (probably better) ways to build counters with Bloom Filters. It’s possible to use bit-arrays for example.

So that’s for the Bloom filter implementation. Now how can we handle that differently?

The user-based approach involves fetching all of the “presentation history” of a user (ie all of the posts that were presented to the user in a feed before) and then going over that list to compute presentation counts for each story.

That’s a little bit more complex than the “muted filter”, because:

• a lot of users have really massive presentation histories, in the tens of thousands or even bigger. Those are readers who come to Medium every day and are exposed to many recommendations
• on average, users have a lot of posts in their presentation histories. Typically less than 100 though. That’s because this includes many less engaged users who only came a handful of times on Medium, and they bring the average down.

So the average cost is going to be higher than for the muted filter because we’re going to retrieve more data from the database AND some users have such big presentation histories that it’s not possible to fetch it in real time. So how can we tackle that?

Here, we’re saved by the fact that this filtering rule is not a hard requirement. Nothing says that “3 presentations is the absolute max” for a given (user, post). We built this rule to make feeds more diverse and less repetitive. We chose 3 as a reasonable default, but it’s okay if in some cases we reach higher counts.

So we can go with a “best effort” strategy here. We fetch the most recent 5k presentations for the user and simply act as if everything before that never existed. DynamoDB queries let us fetch thousands of items quickly, in the ~100ms. So that simple solution is very acceptable in terms of functionality and latencies. There are scenarios where the filter will not be doing its job properly, but they’re limited to certain edge cases with minimal impact on the user.

We tested this approach and found that the costs were reasonable. This solution gives us more flexibility, for instance we can now easily control and play with the maximum number of presentations (is 3 the right threshold? we’ll see that in Part 3). Down the line that will lead to a better experience for users. Now that this filter has been replaced, let’s move on to the final filter, which was the most challenging to migrate.

Replacing the “Read Filter”

Here’s what we’re trying to do:

• we have a shortlist of 1000 stories
• we need to remove all the stories that the user has already read

Very similar to the “Presentation Filter”, the user-based approach for this filter involves fetching the entire reading history of the user. We’re in the same situation where most of the time the user’s reading history is relatively small, with less than 100 posts on average. But we do have some users with massive reading histories.

Fun fact, one of or top readers is our very own Harris Sockel who was in charge of the Medium Newsletter, and had 22k stories in his reading history just for 2024!

This time, filtering already read posts is a hard requirement of the recommendations algorithm, no way around it. We don’t want to send you an email or a push notification about a post you’ve already read.

So what do we do? For this filter specifically we decided to do the filtering in two stages. Very early in the feed building process, we fetch the most recent posts in the user’s reading history (the last 5k posts you’ve read). For the vast majority of users, this will capture their entire reading history. And we use that to filter out already read posts from the feed (at this point, we can have up to 5k posts in the feed). But that’s not enough, we need to guarantee that there are no read posts in the final results for all users.

So to explain this further, we’ll need to go into our recommendation algorithm in a little bit more detail:

You can see that there are two different filtering steps. What we did is that we split out our “Read Filter” into two different implementations and we added each one at a different step:

We’re doing user-based queries in the early filtering step. This is nice because costs do not depend on the number of posts in the shortlist. Once we’re down to only a few posts, we can perform pairwise (user, post) lookups.

This solution works really well and doesn’t add too much complexity to the recs logic. This did require some gymnastics to maintain the requirements while keeping costs, recs performance and latencies under control. But this is much easier to control and debug than the previous implementation with Bloom Filters. It also allows to support things like clearing the reading history for a given user (you can do that from this page to get a “recs fresh start” on Medium). This is a functionality that didn’t work well with the Bloom Filter implementation.

Conclusion

All in all we were able to get rid of our Bloom filters entirely, resulting in big cost savings. The new implementation is ten times cheaper than what our Bloom filters were costing us.

This isn’t necessarily a fair comparison since our Bloom filters had grown out of proportion. If we had migrated from scratch to a new Bloom instances, the Bloom filter implementation might have been cheaper. It was hard to evaluate it in our situation because of the way we built our Bloom filters. We used a single instance and string prefixes to manage all of the different filters.

If we go back to our club and bouncer analogy, you can see it that way: let’s say there’s different crowds that go to the club, techno lovers, jazz enthusiasts, disco heads…

A. you can build a single club that hosts everyone. A single bouncer has the responsibility to memorize all the people in the club

B. or you can build one club for each crowd, each one with a different bouncer

If one day you don’t care about jazz enthusiasts anymore, with B. you can just retire the jazz club and it’s bouncer. But with A. you still need the bouncer for the other crowds, so you can’t retire the bouncer and it’s still holding the information about all the jazz enthusiasts that entered the club. Down the line you might be paying for a club that’s bigger than you need with approach A. With approach B. you pay exactly for what you need!

With Bloom filters it looks like this:

We were working with a single gigantic Bloom Filter, this meant that we weren’t able to retire anything and our Bloom Instance was ever-growing.

The bottom line is that this project helped us get our costs down and migrate to newer, more flexible implementations that are much easier to maintain. With our newer implementations:

• costs are easy to understand and are under control
• filtering costs don’t depend on the initial size of the feed “shortlist”
• there’s no need to maintain derived data

This also laid the groundwork for experiments on our filtering rules that we’ll see in our Part 3: Hard vs Soft Filtering and how this applies to Medium’s Recommendation System.

Thank you for reading this serires, you can stay tuned for the next installments of this series by following the Medium Eng Blog.

Engineering stories behind the Medium Daily Digest Algorithm: Part 2 was originally published in Medium Engineering on Medium, where people are continuing the conversation by highlighting and responding to this story.