Design a news feed

A news feed is your social network's "For You" page. It displays your friends' updates.

The System Design Interview book provides a straightforward solution without many details. Hello Interview's version provides more depth.

Scope

A mobile/web interface that supports posting and retrieving media-rich posts from up to 5,000 friends in reverse chronological order.

APIs

1. POST /v1/me/feed

2. GET /v1/me/feed

Pull / Push

Updates will be in the form of fan-outs, where a single action triggers a waterfall of updates. The trigger can be either on read (GET) or on write (POST).

Pull (read) updates are resource-conservative but can potentially be slow. Push (write) updates will be resource-heavy, but reads will be fast and always up to date. Given there are always more reads than writes, push could be the way to go. It also avoids the sluggish refresh on pull waterfall of queries to get your friend's updates.

The book uses a complicated system: a graph DB with a multi-tiered caching scheme and a hybrid pull/push approach.

The Hello Interview version that follows uses an elegant DynamoDB design to solve the same problem. No graph DB, just two tables and two GSIs.

DynamoDB

DynamoDB is Amazon's serverless NoSQL datastore that lets you store documents by a partition key (PK) and a sort key (SK). You can vary the sort key with local secondary indexes (LSIs). You can also vary the partition key of your data with global secondary indexes (GSIs).

We have a Posts table with a PK of postId along with userId. We have a GSI on Posts with userId as the PK and createdAt as the sort key.

Similarly, we maintain user follow lists in a Follows table and the reverse (followers) in its GSI.

For a given user, we first request all of the users they follow from the Follows table. Then we request all the posts from those N users from the Posts table via its GSI. Then we sort all of those posts by timestamp and return the results to the user!

This is the gist, but the article goes into various deep dives using caches and precomputed feeds to deal with uneven reads and writes.

It's definitely a worthwhile read.

Happy Hackin'!

References

• Facebook news feed via Hellointerview.com

• AWS: DynamoDB global secondary indexes

---

This article is part of the system design series where I am summarizing chapters from The System Design Interview: Volume 1 / Volume 2 amongst other related content