Kiến trúc hệ thốngThiết kế timeline và tìm kiếm của Twitter

Thiết kế timeline và tìm kiếm của Twitter

Nội dung bài

Thiết kế timeline và tìm kiếm của Twitter

Bài tập22 phút đọcThe System Design Primer - bài giải "Design the Twitter timeline and search"

Mục lục
  1. Nội dung gốc
  2. Bước 1: Phác thảo các trường hợp sử dụng và ràng buộc
  3. Bước 2: Tạo thiết kế tổng quan
  4. Bước 3: Thiết kế các thành phần cốt lõi
  5. Bước 4: Mở rộng thiết kế
  6. Các điểm thảo luận bổ sung
  7. Ghi chú của người dịch

Thiết kế timeline và tìm kiếm của Twitter

Nội dung gốc

Lưu ý: Tài liệu này liên kết trực tiếp tới các phần liên quan trong các chủ đề system design để tránh lặp lại. Hãy tham khảo nội dung được liên kết để nắm các điểm thảo luận chung, các đánh đổi (tradeoff) và phương án thay thế.

Thiết kế news feed của Facebook và Thiết kế chức năng tìm kiếm của Facebook là những câu hỏi tương tự.

Bước 1: Phác thảo các trường hợp sử dụng và ràng buộc

Thu thập yêu cầu và khoanh vùng bài toán. Đặt câu hỏi để làm rõ các trường hợp sử dụng (use case) và ràng buộc (constraint). Thảo luận các giả định.

Vì không có người phỏng vấn để trả lời các câu hỏi làm rõ, chúng ta sẽ tự định nghĩa một số trường hợp sử dụng và ràng buộc.

Các trường hợp sử dụng

Chúng ta khoanh vùng bài toán, chỉ xử lý các trường hợp sử dụng sau

Ngoài phạm vi

Ràng buộc và giả định

Nêu các giả định

Chung

Timeline

Tìm kiếm

Tính toán mức sử dụng

Hãy hỏi rõ người phỏng vấn xem bạn có nên thực hiện các phép ước lượng nhanh (back-of-the-envelope) hay không.

Bảng quy đổi tiện dụng:

Bước 2: Tạo thiết kế tổng quan

Phác thảo thiết kế tổng quan (high level design) với tất cả các thành phần quan trọng.

Thiết kế tổng quan Twitter

Bước 3: Thiết kế các thành phần cốt lõi

Đi sâu vào chi tiết từng thành phần cốt lõi.

Trường hợp sử dụng: Người dùng đăng một tweet

Chúng ta có thể lưu các tweet của chính người dùng để dựng user timeline (hoạt động của người dùng) trong một cơ sở dữ liệu quan hệ (relational database). Chúng ta nên thảo luận về các trường hợp sử dụng và đánh đổi giữa việc chọn SQL hay NoSQL.

Việc giao tweet và dựng home timeline (hoạt động của những người mà người dùng đang theo dõi) khó hơn. Phát tán tweet tới tất cả follower (60 nghìn lượt giao tweet qua fan-out mỗi giây) sẽ làm quá tải một cơ sở dữ liệu quan hệ truyền thống. Có lẽ chúng ta sẽ muốn chọn một kho dữ liệu ghi nhanh như cơ sở dữ liệu NoSQL hoặc bộ nhớ đệm trong RAM (Memory Cache). Đọc tuần tự 1 MB từ bộ nhớ mất khoảng 250 micro giây, trong khi đọc từ SSD lâu hơn 4 lần và từ ổ đĩa cứng lâu hơn 80 lần.1

Chúng ta có thể lưu media như ảnh hoặc video trên một kho lưu trữ đối tượng (Object Store).

Fan-out on write: một tweet ghi vào nhiều home timeline Tweet mới Fan Out Service O(n) lượt ghi Timeline A Timeline B Timeline C …
Một tweet mới đi qua Fan Out Service rồi được ghi vào home timeline của từng follower — số lượt ghi tỉ lệ thuận với số follower (O(n)).

Hãy hỏi rõ người phỏng vấn bạn cần viết bao nhiêu code.

Nếu Memory Cache của chúng ta là Redis, ta có thể dùng kiểu list gốc của Redis với cấu trúc sau:

           tweet n+2                   tweet n+1                   tweet n
| 8 bytes   8 bytes  1 byte | 8 bytes   8 bytes  1 byte | 8 bytes   8 bytes  1 byte |
| tweet_id  user_id  meta   | tweet_id  user_id  meta   | tweet_id  user_id  meta   |

Tweet mới sẽ được đặt vào Memory Cache, nơi dựng nên home timeline của người dùng (hoạt động của những người mà người dùng đang theo dõi).

Chúng ta sẽ dùng một REST API công khai:

$ curl -X POST --data '{ "user_id": "123", "auth_token": "ABC123", \
    "status": "hello world!", "media_ids": "ABC987" }' \
    https://twitter.com/api/v1/tweet

Phản hồi:

{
    "created_at": "Wed Sep 05 00:37:15 +0000 2012",
    "status": "hello world!",
    "tweet_id": "987",
    "user_id": "123",
    ...
}

Với giao tiếp nội bộ, chúng ta có thể dùng lời gọi thủ tục từ xa (Remote Procedure Call - RPC).

Trường hợp sử dụng: Người dùng xem home timeline

REST API:

$ curl https://twitter.com/api/v1/home_timeline?user_id=123

Phản hồi:

{
    "user_id": "456",
    "tweet_id": "123",
    "status": "foo"
},
{
    "user_id": "789",
    "tweet_id": "456",
    "status": "bar"
},
{
    "user_id": "789",
    "tweet_id": "579",
    "status": "baz"
},

Trường hợp sử dụng: Người dùng xem user timeline

REST API sẽ tương tự home timeline, chỉ khác là mọi tweet đều đến từ chính người dùng thay vì từ những người mà người dùng đang theo dõi.

Trường hợp sử dụng: Người dùng tìm kiếm theo từ khóa

REST API:

$ curl https://twitter.com/api/v1/search?query=hello+world

Phản hồi sẽ tương tự home timeline, chỉ khác là gồm các tweet khớp với truy vấn đã cho.

Bước 4: Mở rộng thiết kế

Xác định và xử lý các điểm nghẽn (bottleneck), dựa trên các ràng buộc.

Thiết kế Twitter sau khi mở rộng

Quan trọng: Đừng nhảy thẳng từ thiết kế ban đầu sang thiết kế cuối cùng!

Hãy nói rằng bạn sẽ 1) Benchmark/kiểm thử tải (Load Test), 2) Profile để tìm điểm nghẽn, 3) xử lý các điểm nghẽn trong khi đánh giá các phương án thay thế và đánh đổi, và 4) lặp lại. Xem Thiết kế một hệ thống mở rộng tới hàng triệu người dùng trên AWS để có ví dụ về cách mở rộng thiết kế ban đầu theo từng bước lặp.

Điều quan trọng là thảo luận những điểm nghẽn bạn có thể gặp với thiết kế ban đầu và cách xử lý từng điểm. Ví dụ, việc thêm một bộ cân bằng tải (Load Balancer) với nhiều Web Server giải quyết được vấn đề gì? CDN? Bản sao Master-Slave (Master-Slave Replicas)? Mỗi thứ có những phương án thay thế và đánh đổi nào?

Chúng ta sẽ đưa vào một số thành phần để hoàn thiện thiết kế và xử lý các vấn đề về khả năng mở rộng. Các bộ cân bằng tải nội bộ không được vẽ ra để hình đỡ rối.

Để tránh lặp lại các thảo luận, hãy tham khảo các chủ đề system design sau để nắm các điểm thảo luận chính, đánh đổi và phương án thay thế:

Fanout Service là một điểm nghẽn tiềm năng. Những người dùng Twitter có hàng triệu follower có thể mất vài phút để tweet của họ đi hết quá trình fan-out. Điều này có thể dẫn tới tình trạng tranh chấp (race condition) với các @reply cho tweet đó, mà ta có thể giảm thiểu bằng cách sắp xếp lại thứ tự tweet tại thời điểm phục vụ (serve time).

Chúng ta cũng có thể tránh fan-out tweet của những người dùng có rất nhiều follower. Thay vào đó, ta có thể tìm kiếm để lấy tweet của những người dùng này, gộp kết quả tìm kiếm với kết quả home timeline của người dùng, rồi sắp xếp lại thứ tự tweet tại thời điểm phục vụ.

So sánh chi phí: fan-out lúc ghi (push) nặng lúc đăng, fan-out lúc đọc (pull) nặng lúc đọc Fan-out on write (push) Đăng: ghi vào timeline của N follower · O(N) Đọc: lấy danh sách có sẵn · O(1) Fan-out on read (pull) Đăng: lưu 1 bản ghi · O(1) Đọc: gộp tweet của M người mình theo dõi · O(M)
Fan-out on write dồn chi phí vào lúc đăng (ghi vào timeline của N follower); fan-out on read dồn chi phí vào lúc đọc (gộp tweet của M người mình theo dõi) — mô hình lai dùng cả hai tuỳ loại tài khoản.

Các tối ưu bổ sung gồm:

Chúng ta cũng sẽ muốn xử lý điểm nghẽn ở cơ sở dữ liệu SQL.

Mặc dù Memory Cache sẽ giảm tải cho cơ sở dữ liệu, nhưng khó mà chỉ riêng các bản sao đọc SQL (SQL Read Replicas) là đủ để xử lý các lần trượt cache (cache miss). Có lẽ chúng ta cần áp dụng thêm các mẫu mở rộng SQL khác.

Lượng ghi lớn sẽ làm quá tải một cụm SQL Write Master-Slave duy nhất, điều này cũng cho thấy cần thêm các kỹ thuật mở rộng:

Chúng ta cũng nên cân nhắc chuyển một phần dữ liệu sang cơ sở dữ liệu NoSQL.

Các điểm thảo luận bổ sung

Các chủ đề bổ sung để đi sâu, tùy theo phạm vi bài toán và thời gian còn lại.

NoSQL

Bộ nhớ đệm (Caching)

Bất đồng bộ và microservices

Giao tiếp

Bảo mật

Tham khảo mục bảo mật.

Các con số độ trễ

Xem Các con số độ trễ mà mọi lập trình viên nên biết (Latency numbers every programmer should know).

Liên tục

Nguồn: The System Design Primer - bài giải "Design the Twitter timeline and search" — Donne Martin và cộng đồng đóng góp

Giấy phép: CC BY 4.0 (nguyên bản: Donne Martin, The System Design Primer)

Xem bản gốc

Bài tiếp theoThiết kế một web crawler