RecSys · textbook
Trainer Widgets Revision About All chapters ← Data System design →

Part V · Engineering · chapter 18 of 19

Runtime

The last technical chapter — about how everything above works under load without falling over. There is little mathematics here and many decisions, each of which tells an interviewer whether the person has worked with a live system: where to cut the services apart, where to put the filters, what to cache and what to show when half the stack is unavailable.

What to take away
  • Services are split apart because of a different load pattern. At eight replicas the monolith holds 832 GB against 232, and the whole difference is extra copies of one index.
  • Filtering belongs immediately after candidate generation. A late filter at 30% rejection gives 43% fewer useful candidates for the same budget.
  • The better the cache was working, the harder the blow when it is dropped. At a hit rate of 0.95 a mass invalidation gives the layer below a 20-fold spike.
  • A system should not die heroically — it should degrade predictably. A chain of five services at 0.999 each gives 43.7 hours of downtime a year.

1. The architecture of the service

The basic version everyone starts from: an index of items lives on the service and is refreshed once a day; the index holds everything needed to run the models; a request arrives — we go to the profile service, pull up candidates, compute features, run the model, return the answer.

Three bottlenecks
  1. A daily refresh is unrealistic for some products — news, for instance.
  2. One service does all the work: difficulties with parallelism and resilience, the risk of turning into a legacy monolith, hard to work on with a large team.
  3. Memory. The answer has to come in 50–300 ms; if there are many items, fitting them all into the memory of one machine is hard, and reading a lot of data from disk in the runtime is suicide.

Why candidate generation and features are split out

The main reason is a different load pattern

Features and models are bound by CPU and GPU (features partly by memory too). Candidate generation is bound by memory, and its pattern of memory use is a different one.

Keeping this in one process means the service needs a lot of memory and a lot of computation at the same time. Such a service is hard to scale horizontally: adding replicas for the sake of CPU duplicates the whole index along with them.

What that costs

A candidate index of 100 GB per replica, the feature and model layer 4 GB. Two replicas are enough to make the index reliable, while the compute layer is scaled with the load:

Replicas for CPUMonolithSplit apartSaving
2208 GB208 GB
4416 GB216 GB1.9 times
8832 GB232 GB3.6 times
161664 GB264 GB6.3 times

The numbers are reproduced by the script _tools/runtime_demo.py in this repository.

At eight replicas the difference is six extra copies of one and the same index. And note the shape of the dependence: at two replicas there is no gain at all, and beyond that it grows linearly. Splitting apart does not pay off immediately, and that is an honest argument for starting with a monolith.

The other reasons are the standard ones: separation of responsibility, removing a single point of failure, the ability to experiment without touching your neighbour, a natural boundary between teams. The price — features separate from candidates means part of the data may be duplicated in memory; in practice that is accepted.

Fresh items and a dynamic index

What happens when a new item appears: it travels through the event queue, a content embedding is built from its title, description and picture, and the item goes into a separate index that is used in candidate generation.

The practical route: the main service returns its own candidates, a separate «fresh» service returns only fresh ones, and the blender mixes them in a controlled way.

Why fresh items need a separate service if the features are in a lambda anyway

A fair question, and the answer is the same as for splitting out candidate generation at all: it is about the load pattern and about isolation.

In the simple version the fresh service works as a source of fresh candidates — a trending top and the like. In the complex one it does its own ranking with its own rules: cold items have a different set of available features, and mixing them into the main ranker is inconvenient.

It also gives isolation of failures: the index of fresh items is updated constantly and therefore breaks more often, and it should not go down together with the main output.

When memory is short even after the split

VariantWhat we doWhen
Prefilteringpick the subset of items that may be recommended at all: only relatively new ones (news) or a cut-off by predicted non-personal usefulnesswhen the catalogue knowingly holds a lot of junk
Shardingsplit the items into \(X\) pieces, build an essentially independent system inside each, and put an orchestrator on topwhen the catalogue is large and homogeneous
orchestrator / blender merging shards + heavy ranking Shard 1 candidate service · memory feature service · CPU Shard 2 candidate service feature service Shard N candidate service feature service sharding the inference server makes no sense — but several parallel ones give throughput
The second reason to shard is not only memory: parallel shards let more candidates be scored in total.

In practice sharding is most often used together with prefiltering rather than instead of it.

2. Where to filter

We spoke of shards as though candidates had to be generated over all the items. In practice that is not so: some goods must never be shown, some must not be shown to a particular user, some are out temporarily (not in stock), and a mechanism for banning an item instantly is almost always needed.

The right answer: immediately after candidate generation

Let the ranking budget be 500 candidates and let the filters reject 30%.

filtering after ranking500 were scored, 350 survived
filtering right after candidate generation500 valid ones were scored
gain in useful candidates43%

The numbers are reproduced by the script _tools/runtime_demo.py.

A late filter has two troubles, and both are concrete.

  1. We will spend expensive inference time on items we know in advance we will not show. We could have spent it on other candidates — the output would then be strictly no worse.
  2. The output may come out short. To guarantee 20 positions at 30% rejection you have to score 29; otherwise there is a follow-up request, which increases the total response time.

The next question is how to guarantee that exactly \(X\) candidates are ranked. Two options: collect with a margin, or arrange candidate generation itself so that candidates are generated already filtered. The second is better by the same logic — do not waste work — but it is more expensive to implement.

Restrictions come in two types: global availability and content availability broken down into clusters. Where we can, we support light filtering on bitsets or Bloom filters; but sometimes a separate index has to be built per availability cluster, and that is expensive.

3. Caching

Data flies endlessly across the network between services, and the answer, as always, is caching. The simple case is non-personal search, where the whole answer can be cached. But even a personal one almost certainly has a non-personal part: in the chain «relevance model → purchase model», for example, the first does not depend on the user at all.

What to cache in the general case is essentially a product question. The safe baseline: item features with a sensible TTL. The more interesting one: arrange candidate generation so that one part of it explicitly corresponds to the user's long-term interests — and cache exactly that part.

The safety rule: do not invalidate the whole cache at once

The mechanics are simple: on a mass invalidation all the traffic goes down the stack at once, and the stack is not ready for it.

Hit rateShare of requests going down the stackSpike when the cache is dropped
0.500.502 times
0.800.205 times
0.900.1010 times
0.950.0520 times
0.990.01100 times

The numbers are reproduced by the script _tools/runtime_demo.py.

Note the shape of the dependence — it is counterintuitive and therefore dangerous. The better the cache was working, the harder the blow when it is dropped. A system with a hit rate of 0.99 looks healthier than one at 0.90, while in fact it sits on a powder keg: the layer below is scaled for a percent of the traffic.

Hence two rules: choose the cache keys carefully and write separate tests for this. Invalidating the entire cache is not «we will answer more slowly», it is an outage.

About metadata

A recommender service returns simply an ordered list of identifiers. Items reach the screen already with a pile of metadata — a picture, a title, a description. That is achieved in two ways.

The good one: a separate service on top takes care of it.

The historical one: a special kind of request into the recommender system itself, asking it to return the metadata for the required items. It grows out of the temptation to reuse the feature store for that — everything is lying there already, after all.

The second route opens up extra possibilities, but it is usually not worth taking: it binds the lifecycle of the storefront to the lifecycle of the recommendations, and in the long run that is expensive.

4. The Bloom filter and pagination

How it works

A data structure with the interface: insert() in \(O(1)\) and maybe_has() in \(O(1)\). If it answered «no» — the element is definitely absent; if «yes» — the element may still be absent. The error is one-sided, and that is the key property.

The construction: \(k\) independent hash functions with image \([0, m-1]\) and an array of length \(m\) of zeros and ones. On insertion we set ones at the positions given by the hashes; on a check we look at the same positions — if there are ones everywhere, we say «present».

$$ p \approx \Bigl(1 - e^{-kn/m}\Bigr)^{k}, \qquad k^{*} = \frac{m}{n}\ln 2 $$
Why the error curve is U-shaped

An array of 8000 bits, a thousand elements inserted:

Hash functions \(k\)1246812
false positives11.75%4.89%2.40%2.16%2.55%4.83%

The numbers are reproduced by the script _tools/runtime_demo.py; the same script independently repeats the widget's computation.

Too few hashes and there is little discriminating power; too many and the filter fills up with bits. The optimum here is \(k^{*} = 5.55\), and at it exactly half the bits are occupied — a neat and easily remembered sign that \(k\) has been chosen right.

Memory: 8000 bits is 1.0 KB against 7.8 KB for a thousand identifiers of 8 bytes, a saving of 8 times, and it grows with the number of items shown.

Why this is in recommendations: pagination

The usual idea of pagination: we showed the first \(X\) goods, then the next \(X\). The problem is that a recommender system is unstable — between requests the features, the model and the index all change — and a naive implementation leads to duplicates.

An elegant solution: throw a serialised object between the frontend and the backend in a separate parameter — a Bloom filter, say — holding everything already served since the first page. Every next page filters out what has been shown, no matter what happened to the model between requests.

And here is why Bloom in particular fits. There are no false negatives: if it said «not seen», it was definitely not seen. So an error is possible only in the direction of «we will hide something extra»: in the worst case we remove a good item from the output, but we never show the same one twice. The one-sidedness of the error matches what is more expensive.

What to look for here
  1. Move \(k\) and watch the U-shaped curve: one hash gives 11.75%, six give 2.16%, twelve give 4.83% again.
  2. Check that at the optimum exactly half the bits are occupied.
  3. Look at the memory: instead of the whole feed served earlier, a compact filter of a few kilobytes travels with the user.

What to say in an interview: «Bloom gives one-sided errors, and that is exactly what deduplicating the output needs: erring towards „we will hide something extra“ is cheaper than showing a duplicate».

5. Blending and a PID controller

Blending has come up already — as the merging of data from different shards and different sources. But most often it does not end there: sometimes you have to guarantee a fixed share of certain items in the output — ads, fresh items, a particular category.

Why not a hard quota

A hard quota inserts items at fixed positions and destroys the sense of the output. A controller instead tweaks a bonus to the score for the category in question — the output stays sorted by meaning, while the share converges to the target.

$$ u(t) = K_p\, e(t) + K_i \int_0^t e(\tau)\,d\tau + K_d\, \frac{d e(t)}{dt} $$

where \(e(t)\) is the error, that is, the difference between the target share and the actual one.

  • P — a reaction to the current error: the larger the difference, the stronger the action.
  • I — a reaction to the accumulated error: so as actually to reach the target rather than hover near it.
  • D — a reaction to the rate of change of the error: it damps overshoot.
Why it does not work without the integral part

The target is 30% of the category in the output; the natural share without a boost is 10%; at step 60 demand sags.

PIAverage share at the endMiss from the target
0.80.0012.3%−17.7 pp
2.00.0017.3%−12.7 pp
0.80.1528.9%−1.1 pp
3.00.1529.1%−0.9 pp

The numbers are reproduced by the script _tools/runtime_demo.py.

The main thing here is the first row. At \(I = 0\) the share stabilises at 12% instead of 30%: a miss of 17.7 pp. The cause is not a weak setting but the construction of a proportional controller — it produces an action proportional to the error. So at zero error there is no boost either, and the system is forced to live with a permanent shortfall. That is steady-state error.

Raising \(P\) to 2 reduces the miss to 12.7 pp but does not remove it — only shrinks it, adding oscillations in exchange. Steady-state error is removed exclusively by the integral part.

With \(I = 0.15\) the smoothed share reaches a corridor of ±2 pp and never leaves it again. And after the shock at step 60 the share drops to 20%, but the integral picks the boost up and returns it to 29% — a static quota cannot do that: it does not know demand has changed.

And the flip side: at \(P = 3\) the peak of the run-up reaches 58% against a target of 30% — an overshoot of 28 pp, the loop swings.

What to look for here
  1. Set \(I = 0\): the share stabilises away from the target. Convince yourself that raising \(P\) does not remove the miss.
  2. Bring \(I\) back — the share reaches the target.
  3. Raise \(P\) to 3: the loop swings.
  4. Switch the shock off and on: with the integral part the controller returns to the target on its own after demand falls.

What to say in an interview: «A PID is kept in blending because the share of a category depends on demand, and demand changes. P reacts fast but always undershoots; I finishes the job; too large a P makes the output swing».

6. Resilience

The most important rule of the chapter

A system should not die heroically — it should degrade predictably.

The possible troubles: the candidate service died; the feature store is unavailable; the model did not load; a shard fell off; the data is stale; everything is alive but we are not fitting into the budget. In all these cases returning a server error is definitely the worst option.

Why this is not a rare case
Services in the chainEach at 0.999Each at 0.9999Downtime a year at 0.999
10.999000.999908.8 h
30.997000.9997026.3 h
50.995010.9995043.7 h
100.990040.9990087.2 h

The numbers are reproduced by the script _tools/runtime_demo.py.

A chain of five services with a very decent availability of 0.999 each gives 43.7 hours of downtime a year. Without fallbacks those are hours the user sees as an error. With fallbacks they are hours of degradation: the output is worse, but it exists.

And note that the split into services from section 1 worsens this arithmetic. Flexibility of scaling is paid for with the number of places that can break — which is exactly why fallbacks are not an option but part of the same architectural bargain.

the full scenario where we should be most of the time the blender is in pain switch off the late re-ranking stages candidates are in pain an emergency ANN or popularity at the blender the pumpkin precomputed popular items, editorial lists degree of degradation → the transitions between steps are better thought through in advance, not improvised during an incident
Every step answers a particular failure. How the system switches between them is worth designing separately.
About pumpkins

A pumpkin is a deliberately unintelligent but definitely working mode: popular goods computed once (once!), popular by segment, editorial lists, simple business logic with no personalisation.

  • The dumber your pumpkin, the better. There is nothing less pleasant than finding out at the decisive moment that the pumpkin does not work.
  • For a hard incident it is better simply to fix a huge list of items in the config, so that they are certain to fly through every filter.
  • Or to have several pumpkins in sequence.

A thought worth carrying away word for word: if you have not tested your pumpkin in a long time, you most likely no longer have one.

And it is not enough to invent fallbacks — you have to learn to switch them on correctly. Circuit breakers on the calls help, as does tying them to utilisation, and the golden rule: build the pumpkins outside your service. If the service is down, it will not be able to serve even a pumpkin.

7. What to monitor

The ordinary technical onesThe ones specific to recommendations
latency p50 / p95 / p99; the share of errors and timeouts; cache hits; queue lags the share of the different candidate sources in the output; the share of fresh items; the share of fallback answers for each fallback; the coverage of the output and the session by categories; the age of the model, the index and the features; feature coverage and drift
An abstraction worth using: monitor the funnel

It is useful to have monitors not only on the final output but on every one of its stages. Literally:

  • how many candidates were pulled up;
  • how many survived the filtering;
  • how many were scored;
  • how many made it into the answer;
  • how long each stage took.

Such monitoring localises the problem at once. A drop at a particular step is visible instantly, whereas a metric of the final output only says «it got worse» — and then an investigation begins that need not have happened.

Interview questions

Why are candidate generation and features split into separate services?

The main reason is a different load pattern. Features and models are bound by CPU and GPU, candidate generation by memory. In one process the service needs both at once, and it scales horizontally badly: adding replicas for the sake of CPU duplicates the whole index.

The arithmetic: an index of 100 GB, a compute layer of 4 GB. At eight replicas the monolith holds 832 GB and the split system 232 GB, 3.6 times less; the difference is six extra copies of the index.

The other reasons: separation of responsibility, removing a single point of failure, flexibility of experiments, a boundary between teams. The price is possible duplication of part of the data in memory — and at two replicas there is no gain at all.

Where do you put the filters and why?

Immediately after candidate generation. Two reasons.

The first: otherwise we spend expensive inference time on items we know in advance we will not show. With a budget of 500 candidates and 30% rejection a late filter leaves 350 useful ones instead of 500 — that is 43% fewer for the same money.

The second: the output may come out short, which drags the business metrics down. To guarantee 20 positions at 30% rejection you have to score 29, otherwise there is a follow-up request and the response time grows.

The ideal option is to arrange candidate generation so that candidates are born already filtered: no wasted work at all. More expensive to implement.

What is dangerous about a mass cache invalidation?

That all the traffic goes down the stack at once, and the stack is not ready for it. And the dependence is counterintuitive: the better the cache was working, the harder the blow. At a hit rate of 0.95 the layer below is sized for 5% of the traffic and receives 100% — a 20-fold spike; at 0.99 it is 100-fold.

That is, a system with an excellent hit rate looks healthier while in fact being more vulnerable. Hence two rules: choose the cache keys carefully and write separate tests for this. Invalidating the entire cache is not «we will answer more slowly», it is an outage.

How does a Bloom filter work and why is it in recommendations?

k hash functions and a bit array of length m. On insertion we set ones by the hashes, on a check we look at the same positions. The probability of a false positive is \((1 - e^{-kn/m})^k\), the optimum is \(k^* = (m/n)\ln 2\), and at it exactly half the bits are occupied.

The curve over k is U-shaped: at m = 8000 and n = 1000 one hash gives 11.75%, six give 2.16%, twelve give 4.83% again. Too few hashes and there is little discriminating power; too many and the filter fills up.

In recommendations it is for pagination. The system is unstable between requests, so naive pagination produces duplicates; instead a serialised filter with what has already been shown is passed between the frontend and the backend. Bloom in particular fits because there are no false negatives: an error is possible only towards «we will hide something extra», and a duplicate is never shown.

Why is there a PID controller in blending?

To hold the share of a category in the output when demand changes. A hard quota inserts items at fixed positions and destroys the sense of the output; a controller instead tweaks a bonus to the score, and the output stays sorted by meaning.

The key point is why the integral part is needed. A proportional controller produces an action proportional to the error, so at zero error there is no boost either: the system lives with a permanent shortfall. In the simulation, at I = 0 the share stabilises at 12% instead of 30% — a miss of 17.7 pp, and raising P to 2 only reduces it to 12.7 while adding oscillations. Steady-state error is removed exclusively by I.

The flip side is that too large a P makes the loop swing: at P = 3 the run-up reaches 58% against a target of 30%.

What do you do when part of the system is unavailable?

Degrade step by step rather than return a server error. The blender is in pain — switch off the late re-ranking stages and take fewer candidates. Candidate generation is in pain — an emergency ANN or popularity right at the blender. The feature service is in pain — answer with the ANN scores. Everything is in pain — the pumpkin.

Why this is not a rare case: a chain of five services at an availability of 0.999 each gives 0.995, that is, 43.7 hours of downtime a year. And splitting into services worsens this arithmetic — flexibility of scaling is paid for with the number of places that can break.

The transitions between steps have to be thought through in advance, and switched on automatically — with circuit breakers and a tie to utilisation.

What is a pumpkin and how do you work with it?

A deliberately unintelligent but definitely working mode: popular goods computed once, popular by segment, editorial lists, simple business logic with no personalisation.

The rules: the dumber the pumpkin, the better; for a hard incident it is better to fix a huge list of items in the config so that they are certain to fly through every filter; it is useful to have several pumpkins in sequence; and build them outside the main service — if it is down, it will not serve even a pumpkin.

The main thing: if you have not tested your pumpkin in a long time, you most likely no longer have one.

What do you monitor in a recommender service?

Besides the ordinary things (latency by percentile, errors, timeouts, cache hits, queue lags) — the specific ones: the shares of the candidate sources, the share of fresh items, the share of fallback answers for each fallback, the coverage by categories, the age of the model, the index and the features, feature coverage and drift.

And the main abstraction is to monitor the whole funnel: how many candidates were pulled up, how many survived the filtering, how many were scored, how many made it into the answer, how long each step took. Such monitoring localises the problem at once, whereas a metric of the final output only says «it got worse».

One-screen cheat sheet

Different loads

Candidates are memory-bound, models CPU-bound. 8 replicas: 832 GB monolith against 232.

Filters

Right after candidate generation. A late filter at 30% rejection loses 43% of the useful candidates.

Cache

The higher the hit rate, the scarier the drop: at 0.95 a 20-fold spike, at 0.99 a 100-fold one.

Bloom

\((1-e^{-kn/m})^k\), \(k^*=(m/n)\ln2\), half the bits occupied. The error is one-sided.

Pagination

Pass a filter of what was shown between frontend and backend. A duplicate is never shown.

PID

Without I a steady-state error of 17.7 pp. Raising P does not remove it, it only makes things swing.

Degradation

Five services at 0.999 → 43.7 h of downtime a year. Do not die heroically.

The pumpkin

The dumber the better. Outside the service. Not tested means you do not have one.

Primary sources