Facebook News Feed

Requirements (CRUD)

Functional:Create Post Upload Photo/Video, Edit Post, Delete Post, Read Feed, Infinite Scroll, Like, Comment, Share, Follow/Unfollow, Notifications
Non Functional: High Availability Eventual Consistency Low Latency (less than 200 ms feed generation target)

Back of Envelope

World Population      | InternetUsers(60%)    | FB Users(80-85% of Internet users) | Active FB Users(20%)
----------------------|-----------------------|------------------------------------|--------------------
7 Billion //Year 2020 | 7 x 0.6 = 4.2 Billion |    4.2 x 0.8 = 3.5 Billion         | 3.5 x .2 = 700 Million

Traffic Estimates (Incoming Requests/sec) 700 Million pulling their new feed 5 times a day. Total New feed requests = 700 x 5 = 3500 Million requests/day. 3500/24x60x60 = Around 39,000 Requests/sec.
Storage Estimates
Cache/CDN Suppose We want to keep 500 posts/user on CDN for quick fetch. Total posts to be stored. 500 x 700 Million = 350 Billion. Let's assume on average each posts is 1 KB in size. Total bytes = 350 TB Assuming 1 server can cache is 100GB. Total servers needed = 350 TB / 100 GB = 3500 Machines needed in total

API Design


// POST MESSAGE(Image+Text+Video)
POST https://url/v1/post
header { Authorization: {Bearer "API_KEY_TOKEN"},}
body {text, picture_url, video_url}

// READ FEED
GET HTTP/2 https://url/v1/feed
header { Authorization: {Bearer "API_KEY_TOKEN"},}
body {to be filled}

DB Schema

SQL DB

      User information, password, comments can be stored in seperate tables.
      Likes to Comments can be stored in seperate table and comments table can store like_id.


| username | user_id(pk) | created_at | enabled |             //User Table 

| user_id(pk) | password_hash | created_at | expiry_at |      //Password Table

Comments Table: Comment can have text,video,image,@,#,likes,shares
| comment_id (pk) | text_id(fk) | user_id (fk) | media-id(fk) | created_at | like_id(fk) | share_id(fk) |

| key=like_id (pk) | value=file url storing all likes |       //likes Table 

| key=text_id (pk) | value=text url |   //Text Table

Relationship Friends & Friends of Friends stored in TAO(Graph DB)

HLD

Block Diagram

%%{init: {'themeVariables': {'fontSize': '13px'}, 'sequence': {'actorMargin': 45, 'messageMargin': 30, 'boxMargin': 8, 'useMaxWidth': true}}}%%
flowchart LR

%%=========================
%% USER
%%=========================

U([User])

%%=========================
%% EDGE
%%=========================

DNS[Authoritative DNS]

CDN[CloudFront CDN]

WAF[WAF + Shield]

APIGW[API Gateway]

%%=========================
%% SERVICES
%%=========================
subgraph Kubernets Pod
POSTLB[Post Service LB]
POST[Post Service]
POST1[Post Service]
end

subgraph Kubernets Pod
FEEDLB[Feed Service LB]
FEED[Feed Service]
FEED1[Feed Service]
end

subgraph Kubernets Pod
USERLB[User Service LB]
USERSVC[User Service]
USERSVC1[User Service]
end

RANK[Ranking Service]

FANOUT[Fanout Service]

MEDIA[Media Service]

%%=========================
%% CACHE
%%=========================

POSTCACHE[(Redis Post Cache)]

FEEDCACHE[(Redis Feed Cache)]

TAOCACHE[(TAO Cache)]

%%=========================
%% DATABASES
%%=========================

POSTDB[(Post DB)]

POSTREPLICA[(Post Replica)]

TAO[(TAO/MySQL)]

TAOREPLICA[(TAO Replica)]

OBJECT[(Object Storage)]

%%=========================
%% KAFKA
%%=========================

KAFKA[(Kafka)]

%%=========================
%% FLOW
%%=========================

U --> DNS

DNS --> CDN

CDN --> WAF

WAF --> APIGW

APIGW -->|POST /api/v1/posts| POSTLB
APIGW -->|GET /api/v1/feed| FEEDLB
APIGW -->|GET /api/v1/user| USERLB

POSTLB -->|Load balance| POST

FEEDLB -->|Load balance| FEED
USERLB -->|Load balance| USERSVC

POST -->|store image| OBJECT

POST --> POSTCACHE

POST --> POSTDB

POSTDB --> POSTREPLICA

POST --> KAFKA

KAFKA --> FANOUT

FANOUT --> FEEDCACHE

FANOUT --> TAOCACHE

TAOCACHE --> TAO

TAO --> TAOREPLICA

FEED --> FEEDCACHE

FEED --> RANK

RANK --> TAOCACHE

%%=========================
%% COLORS
%%=========================

classDef edge fill:#dbeafe,stroke:#1d4ed8,color:#000;

classDef service fill:#d1fae5,stroke:#059669,color:#000;

classDef cache fill:#fef3c7,stroke:#d97706,color:#000;

classDef db fill:#fce7f3,stroke:#be185d,color:#000;

classDef kafka fill:#fee2e2,stroke:#dc2626,color:#000;

class DNS,CDN,WAF,APIGW edge

class POSTLB,FEEDLB,USERLB,POST,FEED,USERSVC,RANK,FANOUT,MEDIA service

class POSTCACHE,FEEDCACHE,TAOCACHE cache

class POSTDB,POSTREPLICA,TAO,TAOREPLICA,OBJECT db

class KAFKA kafka

Post Upload

TAO Database used for storing relationships

sequenceDiagram

actor User

participant CDN

participant APIGW as API Gateway
box rgb(230,230,255) Kubernets Pod
participant PSLB as Post Service LB
participant POST as Post Service
end

participant OBJ as Object Storage
participant DB as Post DB
participant KAFKA as Kafka
participant FAN as Fanout Service
participant TAO
participant FC as Feed Cache

rect rgb(220,240,255)
User->>CDN: HTTPS POST /api/v1/posts\nJWT + multipart/form-data
CDN->>APIGW: Forward (dynamic request)
APIGW->>PSLB: Route POST /posts
PSLB->>POST: Forward to healthy instance
end

rect rgb(220,255,220)
POST->>OBJ: PUT media object
OBJ-->>POST: mediaURL

POST->>DB: INSERT post(authorId, caption, mediaURL)

DB-->>POST: postId

POST->>KAFKA: Publish PostCreated(postId)

POST-->>User: HTTP 201 Created\n{postId}
end

rect rgb(255,235,220)
KAFKA->>FAN: Consume PostCreated

FAN->>TAO: GetFollowerIds(authorId)

TAO-->>FAN: followerIds

FAN->>FC: Update followers' feed cache
end

Normal Feed Read

TAO Database used for storing relationships

sequenceDiagram

actor User

participant CDN
participant APIGW as API Gateway

box rgb(230,230,255) Kubernets Pod
participant FSLB as Feed Service LB
participant FEED as Feed Service
end

participant CACHE as Feed Cache
participant DB as Feed DB
participant RANK as Ranking Service
participant TAO

rect rgb(220,240,255)

User->>CDN: HTTPS GET /api/v1/feed?page=1

CDN->>APIGW: Forward request

APIGW->>FSLB: Route /feed

FSLB->>FEED: Forward request

end

rect rgb(220,255,220)

FEED->>CACHE: GET feed:user123

alt Cache Hit

CACHE-->>FEED: Candidate Post IDs

else Cache Miss

FEED->>DB: SELECT feed entries

DB-->>FEED: Candidate Post IDs

FEED->>CACHE: Store feed

end

end

rect rgb(255,250,220)

FEED->>RANK: Rank(candidatePosts)

RANK->>TAO: Fetch friend affinity

TAO-->>RANK: Social features

RANK-->>FEED: Ranked posts

FEED-->>User: HTTP 200\nJSON Feed Response

end

Celebrity Sequence

sequenceDiagram

actor Celebrity

participant PostService
participant PostDB
participant Kafka
participant FeedService

Celebrity->>PostService: POST /posts

PostService->>PostDB: Save Post

PostService->>Kafka: Publish PostCreated

PostService-->>Celebrity: 201 Created

Note over Kafka: No fanout to 400M followers

User->>FeedService: GET /feed

FeedService->>PostDB: Fetch celebrity posts

FeedService->>FeedService: Merge with cached feed

FeedService-->>User: Ranked feed

GET Newsfeed

	Push Model	Pull Model
What	Whenever someone posts a item(text, video, audio), Generate newsfeed for all friends/followers and send to friend/follower. Client side browser caches it and delivers when client comes online	Only Generate feed whenever request to retrieve comes from client
Advantage, Disadvatange	Adv: Newfeed is calculated in advance, which leads to very less delay on client to read news feed Disadv: For inactive users/friends also newfeed is calculated. More resources are used upfront	Adv: Newfeed is calculated for active users only, which leads to low resource usage Disadv: Client can get significant latency in receiving newsfeed as its calculated when client asks
Usecase	we use a push model for the majority of users	Celebrity Case: Whenever a celebrity posts a message. Feed for its followers is calculated and delivered.

What we will do?

We will use both of approaches based on the situation. See usecase in above table

Newfeed Architecture