SD12.3 · LESSON 3 OF 6

A feed

Produce an end-to-end design whose data paths, capacities and failure behavior satisfy explicit requirements.

THE IDEA

A feed

Two ways to build a feed. Push on write copies each new post into every follower's feed: cheap to read, but a post by someone with 1,000,000 followers costs a million writes. Pull on read gathers recent posts from every author the reader follows: cheap to write, but a reader following 300 authors costs 300 lookups per open. Because follower counts vary by orders of magnitude, a hybrid pushes for ordinary authors and pulls the celebrities at read time.

author's followers200authors the reader follows300hybrid threshold (followers)10,000

push on write: 1 post → 200 feed writes (reads are then cheap) pull on read: 1 feed read → 300 author lookups (writes are cheap) hybrid: this author has 200 followers → PUSH (threshold 10,000) follower counts differ by orders of magnitude, so one strategy for everyone is rarely best

Change followers, follows and the hybrid threshold.

Predict first. Does every user have the same follower fanout and read rate?

Chapter context

A case study integrates choices into one coherent system. Start with a small requirement set, trace the important operations, calculate the dominant costs and stress the design with a failure before adding components.

TRY IT YOURSELF

Part 1. Do it hands-on

Cost both strategies by hand, then write the cost model and a hybrid planner.

author's followers200authors the reader follows300hybrid threshold (followers)10,000

writes for a 1,000,000-follower post writes for 200 followers lookups per read, 300 follows everyone has the same fanout? (yes/no)

To do: Push on write: each new post is copied into every follower's feed. An author with 1,000,000 followers posts once. Feed writes?
To do: An ordinary author with 200 followers posts once. Feed writes?
To do: Pull on read: a reader following 300 authors opens the feed and the server gathers each author's recent posts. Author lookups per feed read?
To do: Does every user have the same follower fanout and read rate? Type yes or no

Part 2. Do it in code

push_writes(followers): feed writes caused by one post when it is copied to every follower.
pull_reads(follows): author lookups needed to build one feed on read.
daily_push_writes(posts_per_day_by_author): a dict author → (posts_per_day, followers); the total feed writes per day.
daily_pull_reads(feed_reads_per_day, follows): total author lookups per day.
hybrid(authors, threshold): authors is a dict name → followers. Authors with followers <= threshold are PUSHED, the rest are PULLED at read time; return {"push": sorted names, "pull": sorted names}.
hybrid_cost(authors, posts_per_day, threshold, readers_per_day, pulled_authors_per_read_estimate): push writes (sum of followers × posts_per_day over pushed authors) + pull lookups (readers_per_day × len(pull authors) capped at pulled_authors_per_read_estimate per read).

def push_writes(followers):
    pass

def pull_reads(follows):
    pass

def daily_push_writes(posts_per_day_by_author):
    pass

def daily_pull_reads(feed_reads_per_day, follows):
    pass

def hybrid(authors, threshold):
    pass

def hybrid_cost(authors, posts_per_day, threshold, readers_per_day, pulled_authors_per_read_estimate):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Does every user have the same follower fanout and read rate?

AYesBNo

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

For first-completion XP, define a unique logical event key such as (user_id, lesson_id, reward_version). Under a fixed reward r, $XP=r\times$ count(distinct eligible event keys). The deduplication record and awarded effect must share an atomic durable boundary in a real implementation.

Worked example

One hundred learners complete the same lesson, and every completion request is retried once. There are 200 deliveries but only 100 distinct learner-lesson events. At 20 XP per first completion, the correct total is 2000 XP, not 4000. The Python example models the invariant without pretending to implement distributed persistence.

Reference code

The following example uses the Python standard library and does not call a remote service.

deliveries=[]
for user in range(100):
    deliveries.extend([(user,'lesson-1','reward-v1')]*2)
unique=set(deliveries)
assert len(deliveries) == 200
assert len(unique) == 100
assert 20*len(unique) == 2000
assert 20*len(deliveries) == 4000

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

A keyspace count does not prove collision freedom. Delivery and reading are different product events. Deduplication must cover both durable event identity and the actual effect.