1"""Chapter 37 (case study: news feed) deep-dive code.
21. Fan-out on write vs read vs hybrid, at scale, with inactive users skipped.
32. The celebrity problem: write cost of one post.
43. Ranking: affinity x type weight x time decay; candidates then rank.
54. Feed cache and pagination: cursor over a ranking snapshot, so pages don't repeat.
6Run: python3 ch37_news_feed.py"""
7import math
8import random
9
10
11# ---- 1/2. fan-out costs ------------------------------------------------------------
12
13def writes_per_day(posts_per_day, avg_followers, active_share=1.0):
14 return posts_per_day * avg_followers * active_share
15
16
17def celebrity_post_seconds(followers, writes_per_s):
18 return followers / writes_per_s
19
20
21def hybrid_read_cost(followed_celebs):
22 """Pull at read time only from the celebrities you follow."""
23 return followed_celebs
24
25
26# ---- 3. ranking --------------------------------------------------------------------
27
28TYPE_WEIGHT = {"photo": 1.0, "text": 0.7, "link": 0.5, "comment_on_friend": 1.2}
29
30
31def score(post, viewer_affinity, now_h, half_life_h=12):
32 age = now_h - post["at_h"]
33 decay = 0.5 ** (age / half_life_h)
34 return viewer_affinity.get(post["author"], 0.05) * TYPE_WEIGHT[post["type"]] * decay
35
36
37def rank(candidates, affinity, now_h):
38 return sorted(candidates, key=lambda p: (-score(p, affinity, now_h), p["id"]))
39
40
41# ---- 4. pagination -----------------------------------------------------------------
42
43def page_by_offset(ranked, offset, size):
44 return [p["id"] for p in ranked[offset:offset + size]]
45
46
47class FeedSession:
48 """Rank once per session (or per refresh); page through that snapshot with a cursor."""
49
50 def __init__(self, ranked_ids):
51 self.snapshot = list(ranked_ids)
52
53 def page(self, cursor, size):
54 start = 0 if cursor is None else self.snapshot.index(cursor) + 1
55 items = self.snapshot[start:start + size]
56 return items, (items[-1] if items else None)
57
58
59# ---- checks ------------------------------------------------------------------------
60
61def run_checks():
62 # Step 2 arithmetic: 200M daily users, ~1 post each a day on average, 200 followers average
63 raw = writes_per_day(200_000_000, 200)
64 assert raw == 40e9 and round(raw / 86_400) == 462_963 # ~460k feed writes a second
65 active = writes_per_day(200_000_000, 200, active_share=0.5) # skip followers inactive for 30 days
66 assert active == 20e9
67 assert celebrity_post_seconds(50_000_000, 500_000) == 100 # one post, 100 s of fan-out
68 assert hybrid_read_cost(12) == 12 # 12 extra lookups per feed load
69 reads = 200_000_000 * 10 / 86_400
70 assert round(reads) == 23_148 # ~23k feed loads a second
71
72 # ranking
73 rnd = random.Random(37)
74 authors = [f"a{i}" for i in range(50)]
75 affinity = {a: rnd.random() for a in authors}
76 affinity["best_friend"] = 0.95
77 posts = [{"id": f"p{i}", "author": rnd.choice(authors), "type": rnd.choice(list(TYPE_WEIGHT)),
78 "at_h": rnd.uniform(0, 48)} for i in range(300)]
79 posts.append({"id": "bf_old", "author": "best_friend", "type": "photo", "at_h": 20.0})
80 posts.append({"id": "bf_new", "author": "best_friend", "type": "photo", "at_h": 45.0})
81 ranked = rank(posts, affinity, now_h=48)
82 ids = [p["id"] for p in ranked]
83 assert ids.index("bf_new") < 5 # close friend + fresh = near the top
84 assert ids.index("bf_new") < ids.index("bf_old") # same author, older ranks lower
85 # chronological order would put many low-affinity posts first
86 chrono = sorted(posts, key=lambda p: -p["at_h"])
87 chrono_pos = [p["id"] for p in chrono].index("bf_new")
88 assert chrono_pos > 10 and ids.index("bf_new") < 5 # buried in time order, top in ranked order
89
90 # pagination: new posts arrive and ranking shifts between page 1 and page 2
91 page1 = page_by_offset(ranked, 0, 10)
92 posts2 = posts + [{"id": f"new{i}", "author": "best_friend", "type": "photo", "at_h": 48.0} for i in range(3)]
93 reranked = rank(posts2, affinity, now_h=48.2)
94 page2_offset = page_by_offset(reranked, 10, 10)
95 repeats = set(page1) & set(page2_offset)
96 assert len(repeats) >= 3 # offset after re-rank shows repeats
97 sess = FeedSession(ids)
98 p1, cur = sess.page(None, 10)
99 p2, cur = sess.page(cur, 10)
100 assert p1 == page1 and not set(p1) & set(p2) # snapshot + cursor: no repeats
101
102 # feed cache size: 800 post IDs x 8 bytes, for 100M users with a cached feed
103 assert 800 * 8 * 100_000_000 / 1e12 == 0.64 # TB, spread over a Redis cluster
104
105 return {"writes_per_s": round(raw / 86_400), "bf_new_rank": ids.index("bf_new"),
106 "offset_repeats": len(repeats)}
107
108
109if __name__ == "__main__":
110 print("All checks pass.", run_checks())