🎓 A1Learner
🔍
0 of 42 lessons completed

Fan-Out on Read

Fan-out on read is a strategy that builds a user's feed at read time, from the posts of the accounts that user follows. This lesson deep-dives the pull model, the second feed strategy.

A post is stored once

Ana adds a post, and only the post store changes. The printout shows the store and the empty feed store beside it.

posts = {"ana": ["ana: morning run"], "ben": [], "cy": []}
feeds = {}

posts["ana"].append("ana: new photo")

for author in sorted(posts):
    print(author, "stored posts:", len(posts[author]))
print("stored feed lists:", len(feeds))

One read builds the feed

Cy follows ana and ben, so cy's read gathers their posts. The printout shows the merged feed and the posts the read examined.

posts = {
    "ana": [(5, "ana: morning run"), (9, "ana: new photo")],
    "ben": [(7, "ben: hello all")],
    "cy": [(4, "cy: first post")],
}
follows = {"ana": ["cy"], "ben": ["ana"], "cy": ["ana", "ben"]}

examined = 0
gathered = []
for author in follows["cy"]:
    for when, text in posts[author]:
        examined += 1
        gathered.append((when, text))

gathered.sort(reverse=True)
for when, text in gathered:
    print(text)
print("posts examined:", examined)

A new post joins the next read

Ana reads cy's posts, then cy posts again. The second read finds the new post with no feed update in between.

posts = {"ana": [], "ben": [], "cy": [(4, "cy: first post")]}
follows = {"ana": ["cy"], "ben": ["ana"], "cy": ["ana", "ben"]}

def feed_for(user):
    gathered = []
    for author in follows[user]:
        gathered += posts[author]
    return [text for when, text in sorted(gathered, reverse=True)]

print("first read:", feed_for("ana"))
posts["cy"].append((10, "cy: just posted"))
print("second read:", feed_for("ana"))

Example

posts = {
    "ana": [(5, "ana: morning run"), (9, "ana: new photo")],
    "ben": [(7, "ben: hello all")],
    "cy": [(4, "cy: first post"), (8, "cy: market day")],
}
follows = {"ana": ["cy"], "ben": ["ana"], "cy": ["ana", "ben"]}

def read_feed(user):
    examined = 0
    gathered = []
    for author in follows[user]:
        for post in posts[author]:
            examined += 1
            gathered.append(post)
    feed = [text for when, text in sorted(gathered, reverse=True)]
    return feed, examined

for user in ["ana", "cy"]:
    feed, examined = read_feed(user)
    print(user, "feed:", feed)
    print(user, "posts examined:", examined)

Key points

  • Fan-out on read: no feed list is stored for a reader, and the feed is built when the reader opens it.
  • Pull model: the other name for this strategy, because the reader pulls posts together at read time.
  • Post store: each post is stored once, under its author, and copied nowhere.
  • Posting gain: posting writes one post and nothing else, however many followers the author has.
  • Reading cost: one read checks every post of every followed account, then sorts newest first.
  • Fresh read: a post appears in the next read at once, because nothing was copied earlier.

In this example, two reads build two different feeds from the same stored posts. The read for cy examines more posts, because cy follows more accounts.

Note

this strategy trades heavy reads for very cheap posts, the mirror of fan-out on write.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

Under fan-out on read, where does the work of building a feed happen?