System Design Interview 01 - Facebook New Feeds

System Design Interview

Tiếp tục bài 1, câu chuyện phỏng vấn.

X là công ty product sở hữu một mạng xã hội khá có số má, sau vòng phỏng vấn leetcode, ứng viên là một em gái xinh như mộng, đã xuất sắc vượt qua 2 bài programming problem. Tiếp tục là vòng 2, system design interview

Interviewer là anh SA với xx năm kinh nghiệm, nụ cười như mùa thu toả nắng, nhìn em gái trìu mến

Anh muốn thiết kế một trang need feeds chức năng kiểu như Facebook

Functional Requirement

Khi user post status lên thì các friends follower của user đó có thể nhìn thấy status đó

Feeds hiện thị theo reverse chronological order, tức là feed nào mới nhất thì hiện thi trước

Post có thể là text, image, video, link share

Non-Functional Requirement

Feeds hiện thị near-real-time, cho phép latency tầm 1 đến 2s

Khi một status được post lên, max là 5s để hiển thị lên feeds

Dạ thế còn số lượng DAU (Daily active user) và số lượng friend của user

Facebook hiện tại có khoảng 1.3bi DAU, một user cỡ như Messi có thể có 30M follower. Nhưng mình keep simple thôi tầm 10M DAU và 500 follower

Dạ em hiểu rồi ạ, giờ là bước design

Estimate System Capacity

Trong system design, có 1 khái niệm gọi là BACK-OF-THE-ENVELOPE ESTIMATION

Cái tên Back of the Envelope (BotE) có nghĩa là Mặt sau Phong Bì, tức là tính nhẩm các phép đơn giản, có thể viết và tính trên một tờ giấy nhỏ, ngay trên mặt sau của phong bì.

Nói đơn giản, đây là kĩ năng cộng trừ nhân chia ở cấp tiểu học, nhưng lại rất cần thiết trong thiết kế hệ thống.

Ví dụ của BotE trong đời sống

Một em Zalo khoe trên telegram

Em kiếm được 200M/tháng

Để xác định em này có xạo loz hay không hãy áp dụng kĩ năng BotE

Em này một tháng chỉ làm dc 20 ngày, do 10 ngày red light, not avaiable

Giá của em là 500K/shot 30 phút, 1T/1h

Một ngày em làm tầm 10 tiếng, giả sử lúc nào cũng full khách thì tối đa được 10 khách. Một ngày được 10T/max

Vậy 20 ngày ~ 200M là max capacity của em ý, gọi là peak time. Thực tế, thị trường cạnh tranh, rồi các vấn đề thể lực ABC, XYZ thì trung bình độ 50 ~ 70% công suất thôi, average time của hệ thống

Tổng số user là DAU 10, conccurency là 1, nếu có some service 2~3 thì concurency là 2 ~ 3. Việc conccurency là 5 là impossible vì không đủ lỗ, over capacity, nếu đáp ứng phải re-architect lại

Tương tự để xem mấy cái news như kĩ sư lương IT trăm củ, AI 10 Bi/năm thì cứ BotE mà triển

Qua ví dụ trên bạn sẽ thấy việc tính toán BotE không hề phức tạp, chỉ excel thôi nhưng lại tối quan trọng. Giả sử thiết kế một hệ thống, ta ước đoán số lượng người sử dụng là bao nhiêu, dữ liệu cần lưu trữ chiếm dung lượng bao nhiêu, từ đó tính ra cấu hình, xem xét phương án thiết kế cho phù hợp

Rõ ràng nhiều hệ thống có cùng 1 chức năng, nhưng hệ thống có 1K user, thiết kế khác hẳn 1 hệ thống cả tỉ user.

Back về câu hỏi thiết kế hệ thống new feed

Tính toán Storage

Để estimate storage cho hệ thống, người ta dùng công thức Power Of Two, dùng để tính toán bộ nhớ, storage cần thiết, tức là lấy 2 mũ N lần lên để ra dung lượng

Ví dụ 1 post bao gồm

post_id chiếm 64 bytes

text : 140 bytes

media : 1MB

Với 10M DAU, 1 user sống ảo 1 ngày 10 post, khoảng 10% post có chứa media

Vậy media storage = 10^6 * 10 * 10% * 1MB = 100 GB/days, một ngày phải lưu 100GB data media

Còn để estimate cho latency thì dùng bảng công thức của Google

Ví đọc từ caching L1 thì mất 1ns, đọc 1MB data từ SSD là 49us

Tính toán QPS

QPS đo lường hệ thống handle được bao nhiêu request/s hoặc 1 day. Ví dụ server processes 6000 queries in 10 seconds, this QPS là 6000/10= 600

Ở bài toán need feed trên, 1 user 1 ngày request new status độ 10 lần với 10^6 user

QPS = 10e7 requests / 1 day * 24* 3600

Nhìn ở trên thì thấy BotE tuy chỉ tính toán kiểu tiểu học nhưng hệ thống nào cũng cần bước này. Thực tế công việc của tôi, mỗi tháng đều phải làm làm Capacity Reports, ngồi check metrics để xem tháng này hệ thống xử lý bao nhiêu requests, bao nhiêu users, dung lượng lưu trữ bao nhiêu để từ đó điều chỉnh design cho hợp lý đảm bảo cost optimize

Design

Xong khi estimate xong capacity, giờ là thiết kế

Dựa vào chức năng thì hệ thống 2 flow chính

Feed publish: Khi user post status, data sẽ được ghi vào cache và database

Feed fetching: Khi follower/friend của user online, to query data từ cache/database rồi hiển thị lên feed

Tóm lại là 2 flow Đọc / Ghi

Feed publishing API

To publish a post, a HTTP POST request will be sent to the server. The API is shown below:    
POST /v1/me/feed    
Params:    
• content: content is the text of the post.    
• auth_token: it is used to authenticate API requests.    
Newsfeed retrieval API    
The API to retrieve news feed is shown below:    
GET /v1/me/feed    
Params:    
• auth_token: it is used to authenticate API requests

Xài kiến trúc microservice, sương sương 3 em

Post service ghi status vào database
Fanout service push status content vào friends’ feed
Notification service info friends bằng cách push notification

Post service đơn giản là CRUD, request từ frontend đẩy xuống service rồi ghi vào DB

Có Fanout service là điều cần bàn

Fanout on write: user post status phát là thực hiện tính toán generate new feeds cho từng user rồi lưu cache luôn, user bật need feeds thì cứ thế mà load, nhanh gọn real-time. Tuy nhiên cách này gặp user kiểu như Messi, Rolnando có hàng chục M follower thì xác định tốn bộ nhớ và compute resource rõ rệt.

Cơ chế này được Facebook xài

Fanout on Read

Cách này được Twitter sử dụng

Thay vì chơi kiểu thả bom chùm như write, cứ có new posts là generate new feeds luôn, thì chỉ khi nào user online, mở Facebook feeds (read time) mới process feeds. Nhưng vậy sẽ tiết kiệm compute resource cho những follower ảo, ít online. Tất nhiên lúc load new feeds sẽ bị chậm vì lúc đó mới thực hiện tính toán. Do đó có thể thấy hiện Lag khi user load new feeds

2 cách đều có Pros and Cons, nên cách chơi ngon bổ rẻ là hybdrid, tức là user mà có ít bạn, nhiều bạn thân, bạn quen thì Fanout on write, còn user như Messi thì Fanout on read

Như Design

1. Fanout service fetch friends ID từ Database, Friend Info từ Cache, rồi đẩy vào Queue

2. Fanout workers fetch data from the message queue and store news feed data in the news feed cache, theo kiểu appends list

Queue đóng vai trò như bộ đệm, vì số lượng follower, friends rất lớn, Fanout Worker không thể scale vô hạn để handle được

Anh SA nghe xong mỉm cười

Vậy em Scale database như thế nào Vertical hay Horizontall? 

Dùng loại DB ghi, Relational, Graph, NoSQL?

User 10M nên lên 100M user, các service scaling ra sao?

User như Messi, Ronanda thì handle thế nào?

Có post thì nhiều người đọc, nhiều tương tác, có post chả ma nào đọc, generate new feeds thế nào cho tối ưu?

Em sử dụng datastorge nào để lưu trữ dc 100G/ngày

Em gái bẽn lẽn, dạ hẹn anh tối nay tại Love Hotel em trả lời nốt ạ

(Còn tiếp)