Ranking a Feed

Candidate generation against ranking, keeping the model off the request path, and what the feed returns when the ranker is slow.

Syntaxcandidates = generate(userId, max=500); scored = rank(userId, candidates, deadlineMs=60)

Ranking decides the order of a feed. It is a separate concern from building the feed, and conflating the two is the usual reason a feed is both slow and hard to change.

Two stages

The standard structure is the two-stage retrieval split described in the YouTube recommender paper (Covington, Adams and Sargin, RecSys 2016). Candidate generation is cheap and recall-oriented: it reduces a corpus of millions to a few hundred items that are plausibly relevant, using approximate nearest-neighbour lookups over embeddings, recent-follow activity and simple heuristics. Ranking is expensive and precision-oriented: it scores those few hundred with a richer feature set and returns the top tens. The split exists because no model can score a whole corpus per request, and because recall and precision want different features.

Keeping the model off the request path

What happens per request should be a feature lookup and one batched scoring call. Embeddings, candidate sets and aggregate counters are computed by batch or nearline jobs and written to a store the request path only reads. The scoring call gets a hard deadline, in the tens of milliseconds, because it sits inside a user-facing budget.

Falling back

Ranking must be optional. On timeout, error or an empty score vector, return the candidate list in reverse-chronological order and record that you did. A feed that 500s because the ranker is redeploying has made a model a hard dependency of availability.

What trips people up

Training/serving skew: a feature computed one way in the batch job and another way online degrades quality silently, with no error anywhere. Compute each feature once and read it from the same store in both paths.

Example

Example · javascript
// Request path. Two stages, one feature read, one scoring call, hard deadline.
const RANK_DEADLINE_MS = 60;

function withTimeout(promise, ms) {
  // Promise.race resolves with whichever settles first; the loser keeps
  // running but nobody is listening.
  return Promise.race([
    promise,
    new Promise((_, reject) =>
      setTimeout(
        () => reject(Object.assign(new Error("rank deadline"), { name: "RankTimeout" })),
        ms
      )
    ),
  ]);
}

async function buildFeed(userId, limit = 20) {
  // Stage 1: candidate generation. No model call here - these sets are
  // written by a nearline job as posts arrive, so this is a read.
  const candidates = await candidateStore.get(userId, { max: 500 });
  if (candidates.length === 0) return [];

  // Reverse-chronological order is the answer we can always produce. Compute
  // it first, so the fallback path needs no extra work.
  const byRecency = [...candidates].sort((a, b) =>
    a.postId < b.postId ? 1 : a.postId > b.postId ? -1 : 0   // sortable ids
  );

  let ordered = byRecency;
  let ranked = false;
  try {
    // Stage 2: ranking. One batched feature read, one batched score call.
    const features = await featureStore.mget(
      userId,
      candidates.map(c => c.postId)
    );
    const scores = await withTimeout(
      ranker.score({ userId, features }),
      RANK_DEADLINE_MS
    );
    if (scores.length !== candidates.length) throw new Error("score arity mismatch");

    ordered = candidates
      .map((c, i) => ({ ...c, score: scores[i] }))  // spread; same as
      .sort((a, b) => b.score - a.score);           // Object.assign({}, c, {score})
    ranked = true;
  } catch (err) {
    // Degrade the ordering, never the availability.
    metrics.increment("feed.rank.fallback", { reason: err.name });
    ordered = byRecency;
  }

  const page = ordered.slice(0, limit);
  // Log every candidate that was scored and the position it ended up in, not
  // just the ones that made the page: a log of impressions only teaches the
  // next model what this one already chose.
  await rankLog.write({
    userId,
    ranked,
    consideredCount: candidates.length,
    scored: ordered.map((c, position) => ({
      postId: c.postId,
      score: c.score ?? null,
      position,
      shown: position < limit,
    })),
  });
  return page;
}

When to use it

  • Reordering a 500-item candidate set without letting the model touch the 99th-percentile feed latency.
  • Keeping the feed serving reverse-chronologically while the ranking service is redeployed.
  • Diagnosing a quality drop that turns out to be one feature computed differently online and offline.
  • Evaluating a new ranking model on live traffic before it influences a single response.

More examples

Candidate generation as a nearline job

Moves the expensive part out of the request. Each new post updates the candidate sets of users who might see it, so the read path is a single key lookup. Reach for this when candidate generation involves graph traversal or vector search that cannot fit in a request budget.

Example · javascript
// Runs on the post stream, not on reads. Each user's candidate set is a
// capped sorted set, so the read path is one ZREVRANGE.
const CANDIDATE_CAP = 500;

async function onNewPost(post) {
  // Two sources, unioned: people you follow, and topically similar content
  // from an approximate nearest-neighbour index over post embeddings.
  const [followers, similar] = await Promise.all([
    graph.activeFollowers(post.authorId, { limit: 50_000 }),
    ann.query(post.embedding, { k: 200, minScore: 0.7 }),
  ]);

  const audience = new Set(followers);
  for (const s of similar) {
    for (const u of await affinity.usersInterestedIn(s.topicId, { limit: 500 })) {
      audience.add(u);
    }
  }

  const pipe = redis.pipeline();
  for (const userId of audience) {
    const key = `cand:${userId}`;
    // Score is a cheap prior - recency plus author affinity. The ranker
    // refines this; it does not depend on it being good.
    pipe.zadd(key, Number(post.createdAt), String(post.postId));
    pipe.zremrangebyrank(key, 0, -(CANDIDATE_CAP + 1));
    pipe.expire(key, 7 * 86_400);
  }
  await pipe.exec();
}

One feature definition, two paths

The concrete fix for training/serving skew: the transform lives in one function, the batch job writes it, the request path reads it, and a version string makes a change visible instead of silent. Use this the first time a feature's online value disagrees with its training value.

Example · javascript
// A feature is a named transform plus a version. Both the training job and
// the serving path call the same function, so they cannot drift.
const FEATURES = {
  author_affinity_7d: {
    version: 3,
    // Raw counters are produced by the aggregation job; the transform that
    // turns them into a model input lives here and nowhere else.
    compute: ({ interactions7d, impressions7d }) =>
      impressions7d === 0 ? 0 : interactions7d / impressions7d,
  },
  post_age_hours: {
    version: 1,
    compute: ({ createdAt, now }) => (now - createdAt) / 3_600_000,
  },
};

function vectorise(raw, now) {
  const out = {};
  for (const [name, f] of Object.entries(FEATURES)) {
    out[name] = f.compute({ ...raw, now });
  }
  // The model rejects a vector built by the wrong feature versions, which
  // turns a silent quality regression into a loud error.
  out._schema = Object.entries(FEATURES)
    .map(([n, f]) => `${n}:${f.version}`)
    .join(",");
  return out;
}

Shadow-evaluating a new ranker

Sends the same candidates to the current and the candidate model, serves only the current one, and logs both orderings. Reach for this before any ranker change ships: it measures the new model on live traffic without putting it in the latency or availability path.

Example · javascript
// The challenger runs alongside the champion but never affects the response.
async function rankWithShadow(userId, candidates, features) {
  const champion = await withTimeout(
    ranker.score({ userId, features, model: "rank-v7" }),
    RANK_DEADLINE_MS
  );

  // Fire-and-forget, sampled, and explicitly not awaited: the shadow call
  // must not be able to add latency or fail the request.
  if (Math.random() < 0.05) {
    ranker
      .score({ userId, features, model: "rank-v8-candidate" })
      .then(challenger =>
        rankLog.write({
          userId,
          championOrder: argsortDesc(champion),
          challengerOrder: argsortDesc(challenger),
          postIds: candidates.map(c => c.postId),
        })
      )
      .catch(() => metrics.increment("feed.shadow.error"));
  }

  return champion;
}

// Indices of the highest scores first - the ordering the model implies.
const argsortDesc = scores =>
  scores.map((s, i) => [s, i]).sort((a, b) => b[0] - a[0]).map(([, i]) => i);
// Arrow with an implicit return; the same as:
// function argsortDesc(scores) { return scores.map(...)...; }

Related

sd design twittersd design instagramsd timeouts retriessd percentilessd cache strategies

Discussion

  • Be the first to comment on this lesson.