Requirements

Functional Requirements:

• Support both mobile app and website. Scope of this design will focus on backend that's shared across both clients.
• Users have accounts and can upload photos/short videos.
• Users can follow/unfollow other users.
• Users can view their home feed - a personalized, scrolling timeline of posts from followed accounts.
  • Assume: feed is chronologically ordered for now. If time, can explore other sorting approaches.
• Notifications for alerts like follows, likes, comments, etc.
• Users can like and comment posts.
• Out-of-scope extensions unless time: user pages, search, stories, reals, dms.

Non-Functional Requirements:

• Assume 2 billion users, with ~10^9 DAU.

Capacity Estimation

Assumptions:

1. Assume each user posts once a day
2. Views their feed 10x a day

Ignore S3 object costs, that means for just post storage, that's 10^9 users x 1 post/user x 1 KB/post = 10^9 KB of growth for posts table in one day.

Annually, that's 4000 x 10^9 KB = 4 x 10^12 = 4 TB of data. Assuming growth in the other tables, that's ~100 TB growth annually.

In terms of QPS, assuming 100:1 read:write ratio, we assume each user views their feed 10x a day, so 10^9 users x 10 queries = 10^10 QPD 1 day/10^5 seconds = 10^5 QPS = 100,000. Assuming a given server can handle ~2000 QPS, then we need at least 50 servers.

API Design

• api/user POST to create user
• api/user/<user_id>/resource POST to upload photo or short video. body: photo or video, description, tags, other metadata
• api/user/<user_id>/follow POST to follow. body: JSON with account to follow or unfollow and type: (follow/unfollow)
• api/user/<user_id>/feed GET - returns feed
  • Query parameter: before -> opaque token combo of timestamp param that filters out records created after the timestamp + unique id of post (for tiebreaks)
  • Query parameter: num_records -> default to 50.
• api/user/<user_id>/comment POST - BODY: JSON with params , resource id
• api/user/<user_id>/like POST BODY: Json with params (resource id)

High-Level Design

High level architecture:

• Regional deployments with geographic DNS-based routing policy to regional load balancers.
• Application tier: regional load balancers fronting stateless application.

Regional application deployment:

• Database tier: single global managed PostgreSQL instance. Will need to use horizontally sharded PostGre for horizontal scale. Example: 128 TiB limit for single Aurora cluster is exceeded in just a couple years. We will need to use Aurora Limitless, which allows us to shard tables horizontally by specifying a shard key. The max size for a table slice is 32 TiB.
• Store uploads (files, photos) in regional S3 bucket and track metadata in database.
  • For fast cross-region access, can leverage cross-region replication so objects can be accessed from "local" bucket.
• Local caching and Aurora Global Database to speed up reads.
• Use CDN for caching of static content and public objects in front of regional deployments.

Database Design

• Tables: user, resource, comment, like, follows
• user table: table to hold users
  • columns: first_name, last_name, country, address, created, birthdate, gender
• resource table: table to hold photos and videos
  • columns: user_id (owner of resource), type (photo or video), caption, bucket_name, object_key, created
• comment table: table to hold comments on posts
  • unique id, columns: user_id, commenter_id, resource_id, content (comment) text, created, edited
• like table: table to hold likes on posts
  • columns: user_id (user that owns the resource), liker_id (user that liked the resource), resource_id, created
• follow table: table to track follows between users
  • columns: followee_id (user id of the followee), follower_id (user id of the follower), created

Detailed Component Design

1. Implementation for api/user/<user_id>/feed GET - returns feed
   1. Brute-force: for a given user, fetch the ~50 most recent posts from people they follow i.e. SELECT * from resource table where user_id in (set of followee ids) where created < (before) order by created desc, id desc limit 50;
   2. Returns a JSON structure that the client website/mobile app can use to render the feed. A list of objects, each comprising
      1. Presigned URL for client to fetch object from S3 directly
      2. Post creator + caption
      3. created date
      4. number of comments
      5. number of likes
   3. Pagination is implemented by the client specifying the <before> timestamp for subsequent scrolls using the timestamp of the earliest post received in the previous call.

Performance:

• Specify country, user_id as the shard key for (user, resource, comment, like)
• follower table: followee is the shard key
• Further partition resources by date.

Concern:

• The feeds query will result in fan out across shards since data are colocated for a given user. But a feeds requires query resources across multiple users.
• Hotspots: some users (e.g. Justin Bieber) are heavily followed and those shards will experience heavy read-traffic.

Options for feeds reading optimization:

• Proactively maintain a materialized feed and cache it per user. Assuming we cache the feed lazily in a valkey instance (represented as a list of JSON strings) per user. The feed will be maintained with up to a day's worth of data per user.
• Upon initial request, the cache miss will force brute force computation. Read-aside caching ensures the computed value will be placed in the cache.
• Background workers will ensure existing cached feeds stay up to date, by processing a queue of new posts and inserting the entry into list. This works because the system is read heavy rather than write heavy.
• This "write-aside" approach means newsfeeds may be stale, but this is acceptable given the use-case. Eventually the cache will be up to date.