RecSys Supplement · The X algorithm · page 3 of 11
Sources: where the posts come from at all
Before anything can be ranked it has to be found. The feed has seven sources of candidates, and they are built in fundamentally different ways: one keeps posts in RAM, another searches for nearest neighbours in a vector space, a third leans on a clustering of the whole social graph. Let us see why there are so many and why none of them replaces the others.
In brief
- The main division is by follows. Posts from the people you follow are searched for in a fundamentally different way from posts by people you do not follow.
- Thunder keeps fresh posts right in RAM, laid out by author. No search at all: getting the posts of your follows means walking the list of follows and taking ready-made queues.
- SimClusters clusters the social graph into 145 thousand communities by sparse binary factorisation, and then looks for candidates in the space of communities.
- Every source has its own limit: retrieval returns up to 1000 posts, Thunder up to 1200, the rest fewer. The limits are a distribution of budget between ways of searching.
- No source replaces the others, because each sees its own subset and is blind to the rest. This is the same argument as in multi-source retrieval.
1. Why there are several sources
The question is fair: if there is a trained model that can find relevant posts, what else is needed alongside it?
The answer is simpler than it seems: every way of searching has its own blind spot, and they do not overlap.
| Source | What it finds | What it does not see |
|---|---|---|
| Thunder | Everything your follows published in the last few hours | Anything at all outside the follows |
| The retrieval model | Posts similar to what you liked | Very fresh posts that have not reached the index; topics you have no history in |
| SimClusters | Posts popular in the communities you belong to | The niche and the new: the clusters are recomputed once a week |
| Topical sources | Posts on topics you explicitly subscribed to | Everything outside the named topics |
| The cache of ranked posts | What was computed last time | Everything new since the caching |
The second row is especially telling. The retrieval model is excellent, but its index, as we discussed on the page about retrieval, is refreshed only when a checkpoint is saved. A post published five minutes ago is physically absent from it — and it is precisely such posts that make up the feed of a social network.
in the chapter «Kinds of candidate generators» we said that candidate generators are combined not out of poverty but because each is optimised for its own type of connection: the collaborative one catches «similar people watched», the content one «similar in content», the popularity one «this is simply good».
Here it is the same, but the axis is different — by freshness and by type of connection at once. Thunder covers «fresh and from people I know», retrieval «similar to my interests», SimClusters «popular in my community». Remove any of them and a class of posts appears that the system stops finding in principle.
2. Thunder: posts from follows in RAM
The most straightforward and the most instructive source. The task: given a list of follows, return their fresh posts. The solution: do not search at all, but keep everything needed in memory, already laid out by author.
What exactly lies in memory
pub struct PostStore {
posts: Arc<DashMap<i64, Arc<CompactPost>>>,
original_posts_by_user: Arc<DashMap<i64, VecDeque<TinyPost>>>,
secondary_posts_by_user: Arc<DashMap<i64, VecDeque<TinyPost>>>,
video_posts_by_user: Arc<DashMap<i64, VecDeque<TinyPost>>>,
deleted_posts: Arc<DashMap<i64, bool>>,
retention_seconds: u64,
request_timeout: Duration,
}A fragment of post_store.rs · code by X, Apache 2.0, commit 28e414f
Five structures, and every one of them is explicable.
posts— the post itself by identifier. Note the type:CompactPostis a structure of eleven fixed-size fields, with no text. Identifiers, times, the flags «repost», «reply», «has video».- Three separate indexes by author: original posts, secondary ones (replies and reposts) and video. Each holds a queue of
TinyPost, and that is only two fields: the identifier and the creation time. deleted_posts— tombstones for what has been deleted.
It would seem you could keep one list per author and filter on the way out. But then, to return ten original posts by an active author, you would have to read a hundred of their replies and throw them away. With a thousand follows that is a thousand extra passes on every request.
Separate indexes turn filtering into a choice of data structure. Only the original ones are needed — take one queue. Video is needed — another. The work that does not happen is the cheapest work of all.
This is exactly the trick that the chapter «The order of filtering» called «filter at the level of the index, not after the selection». Here you can see what it turns into in practice: not a condition in the code but a decision about the layout of the data.
TinyPost is two eight-byte integers, that is, 16 bytes. CompactPost is eight integers and three flags, on the order of 72 bytes with alignment.
A rough estimate: suppose the system holds 500 million posts within the retention window. The main map is about 36 gigabytes, the indexes by author another 8 gigabytes each. A lot, but that is realistic for one fleet of machines, and orders of magnitude faster than any trip to disk.
And now imagine we decided to keep the text too. An average post is hundreds of bytes, and the estimate grows several times over, to hundreds of gigabytes. That is exactly why there is no text in the structure: Thunder answers the question «which posts», not «what is written in them». The text is pulled in later, by a hydrator, and only for the candidates that survived to that stage.
How this is filled
Thunder is subscribed to a stream of Kafka events: a post was published, a post was deleted, its visibility changed. No periodic dumps — the data arrives continuously, and the delay between publication and the post appearing in memory is measured in seconds.
The old is cleaned out by retention time: there is a background task trim_old_posts that walks the queues and throws away what has fallen outside the window. Plus sort_all_user_posts — a periodic re-sorting, because Kafka events do not arrive in strict order.
in the chapter «Two loops and the lambda architecture» we discussed the split into an offline loop (heavy, batch, precise) and an online loop (light, streaming, fresh). Thunder is a model online loop: it computes nothing, it simply remembers the recent and can return it quickly by key.
Note the division of labour. Thunder knows which posts exist at all among your follows right now. It knows nothing about which of them are good — that is the work of ranking. Every system solves exactly one task, and that is exactly why both come out simple.
3. SimClusters: clustering the social graph
The oldest and the most conceptually interesting source. The idea: if users are split into communities by who follows whom and who interacts with whom, then «what is interesting for you» can be searched for in the space of communities rather than in the space of posts.
The configuration of the model is sewn into the names of the datasets: Model20M145K2020 — 20 million users are laid out across 145 thousand clusters.
Sparse binary factorisation
In the code the method is called SBF, and at its base lies SparseBinaryMatrix. Let us look at how it differs from the familiar matrix factorisation of the chapter «Matrix factorisation».
| Ordinary factorisation | Sparse binary | |
|---|---|---|
| Values of the factors | real numbers | zeros and ones |
| How many non-zero | all \(d\) coordinates | a few out of 145 thousand |
| Meaning of a coordinate | unclear | a particular community |
| What is factorised | the interaction matrix | the similarity graph of accounts |
The key difference is interpretability. A coordinate of an ordinary embedding means nothing; you cannot say of it «this one is about astronomy». A SimClusters cluster means a particular community, it has members, it can be looked at with your own eyes, it can be given a name, it can be complained about.
The second difference is sparsity. An account belongs to a few communities out of 145 thousand rather than having 145 thousand weak weights. That gives both an economy and an inverted index: given a community, everyone in it can be retrieved quickly.
The question is natural: SimClusters is a technology of the previous decade, and a transformer stands right beside it. Three reasons why it was not thrown away.
- It sees something else. Retrieval is trained on your likes and finds things similar to what appealed to you. SimClusters leans on the structure of the social graph: the community you belong to is determined by whom you follow, not by what you liked. These are different signals, and they diverge more often than it seems.
- It is explainable. «This post is popular in a community you belong to» is a phrase that can be shown to a user and presented to a regulator. «The dot product of the embeddings equals 0.83» cannot.
- It is stable. The clusters are recomputed once a week and change slowly. The model is retrained more often and may change its behaviour abruptly. Having in the system a source that moves slowly and predictably is an insurance policy.
It is also an illustration of the thought from the chapter «How to design a system from scratch»: in production, technologies of different generations live side by side, and that is normal. The old is not thrown away while it still covers its niche.
4. Source limits: the distribution of the budget
Every source has a ceiling in the configuration on the number of posts it returns.
| Source | Maximum posts | Comment |
|---|---|---|
| Thunder | 1200 | The most of all: posts from follows are cheap and come out of memory |
| Phoenix retrieval | 1000 | The main source of posts outside the follows |
| Tweet Mixer | 800 | |
| Phoenix MOE | 200 | A separate variety of retrieval |
These numbers are not technical limitations but a product decision expressed in a config. They set what material the system can assemble a feed out of at all.
Consider the proportion: 1200 posts from follows against roughly 2000 from all the other sources. If Thunder returned 5000 and retrieval 200, the feed would be fundamentally different — almost entirely from the follows — with absolutely the same ranking weights and the same model.
When people ask «why does the feed show me so many unfamiliar accounts», they instinctively look at the action weights and at the out-of-network discount. But the source limits influence the composition of the feed earlier and more strongly: what did not get into the candidates cannot be ranked in any way at all.
This is the general rule of multi-stage systems from the chapter «The multi-stage funnel»: the ceiling is set by the first stage. The funnel widget there shows the same thing numerically — end-to-end recall is the product of the stages' recalls, and no ranker wins back the losses of candidate generation.
5. The cache of ranked posts as a source
The CachedPostsSource deserves separate attention. It returns posts already ranked in a previous request.
This is a direct consequence of the isolation of candidates: since the score of a post depends only on the «user and post» pair and not on who else was in the batch, it can be saved and reused. A design decision inside the model turned directly into a source of candidates in the pipeline.
What for: a person scrolls the feed, and every next screen is a new request. Recomputing the model on the same candidates makes no sense. The cache makes it possible to return the continuation instantly and spend the budget on searching for something new.
Note how this ties to rounding the age of a post to the hour in the ranking model: without the rounding the feature would change every minute and a cached score would go stale immediately. Three decisions in three different places of the system — the attention mask, the granularity of a feature and a cache-as-source — work towards one goal.
Common mistakes and hidden rocks
- Thinking that neural retrieval makes the other sources unnecessary. Its index is refreshed when a checkpoint is saved, so the very freshest posts are not in it. And in the feed of a social network it is exactly those that make up the main material.
- Thinking that Thunder is a database. It does not answer arbitrary queries. It can do one thing: given an author, return their recent posts. Everything else is moved outside.
- Storing text where only identifiers are needed. There is no text at all in the Thunder structure — that is the difference between tens and hundreds of gigabytes of memory.
- Not noticing the source limits. The composition of the feed is determined by them earlier than by the weights: a candidate that did not get in cannot be ranked in any way at all.
- Considering SimClusters obsolete. It leans on the structure of the graph rather than on a history of likes; it gives explainability and changes slowly. That is a niche of its own, not a lagging version of retrieval.
Interview questions
Why does a system need several candidate generators if one of them is a trained model?
Each has its own blind spot. The retrieval model looks for things similar to the user's history, but its index is refreshed only when a checkpoint is saved — the very freshest posts are not there. The source of posts from follows sees only the follows. The cluster source leans on the structure of the graph and knows nothing about the new, because the clusters are recomputed once a week.
Remove any one and you get a class of posts the system stops finding in principle. This is exactly the argument about multi-source retrieval from the chapter «Kinds of candidate generators»: different generators are optimised for different types of connection, and their union covers more than the best of them.
How do you return posts from follows in single-digit milliseconds?
Do not search, but keep them in memory laid out by author. In the system we looked at this is a separate service: a map «post identifier → compact record» plus indexes «author → the queue of their recent posts». A request comes down to walking the list of follows and reading ready-made queues.
Three decisions make that possible. No text at all — only identifiers, times and flags, otherwise the memory grows by an order of magnitude. A retention window — the old is cleaned out by a background task. Separate indexes for original posts, replies with reposts, and video — so that filtering is a choice of structure rather than a pass with discarding.
It is filled by a stream of events, not by a periodic dump: the delay from publication to appearance in memory is seconds.
What is SimClusters and how does it differ from matrix factorisation?
It is a clustering of the social graph: 20 million notable accounts are laid out across 145 thousand communities by sparse binary factorisation of the similarity graph. An author gets a set of communities they are known for; a user gets a set of communities they are interested in, as a sum over those they follow; a post gets a vector over communities.
The differences from ordinary factorisation: the values are binary rather than real; there are few non-zero coordinates; and, most importantly, a coordinate is interpretable — it is a particular community with members that can be looked at with your own eyes. Besides, what is factorised is not the interaction matrix but the similarity graph of accounts.
Why keep a source in the system that is recomputed once a week?
For stability and explainability. A slowly changing source is insurance for the case when the model starts behaving unexpectedly after retraining: part of the feed stays predictable.
Explainability matters no less: «this post is popular in a community you belong to» can be shown to a user and presented to a regulator, while «the dot product of the embeddings is 0.83» cannot.
The price is a week's delay: a new account will not get into the clusters at once. That is why the source is not the only one.
Can a computed score be reused on the next request?
Only if the score depends on the «user and post» pair and on nothing else. In the system we looked at that is guaranteed by the attention mask: candidates do not see each other, so the score does not depend on the composition of the batch. Thanks to that, the pipeline has a separate source returning already ranked posts from a cache.
The second condition is that the features must not change faster than the cache lives. That is why the age of a post is fed to the model with a granularity of an hour: a continuously growing value would devalue the cache every minute.
The practical meaning: a person scrolls the feed, every screen is a new request, and recomputing the model on the same candidates makes no sense.
One-screen cheat sheet
The main division
Inside the follows and outside them. Searched for in fundamentally different ways.
Thunder
Fresh posts from follows in RAM, laid out by author. A stream from Kafka.
Compactness
No text: 11 fixed-size fields. The text is pulled in later and only for the survivors.
Three indexes
Original, secondary, video. Filtering as a choice of data structure.
SimClusters
20 mln accounts → 145 thousand communities by sparse binary factorisation of the graph.
KnownFor / InterestedIn
An author is known for communities; a user's interests are the sum over their follows.
Limits
Thunder 1200, retrieval 1000, Tweet Mixer 800, MOE 200. This is a product decision.
The cache as a source
Possible only thanks to the isolation of candidates in the model.
Why not one source
Each has its own blind spot: freshness, history, the structure of the graph.
Primary sources
- thunder/posts/post_store.rs — the structures in memory, the indexes by author, the cleaning out of the old.
- UpdateKnownForSBFRunner.scala — building the communities by sparse binary factorisation.
- InterestedInFromKnownFor.scala — a user's interests from the communities of the authors, the weekly recomputation.
- home-mixer/sources/ — how all the sources are wired into the feed.
- The course: the chapter «Kinds of candidate generators» on kinds of candidate generators, the chapter «Matrix factorisation» on matrix factorisation, the chapter «Two loops and the lambda architecture» on the two loops.