Bài tập·22 phút đọc·The System Design Primer - bài giải "Design Pastebin.com (or Bit.ly)"

Thiết kế Pastebin.com (hoặc Bit.ly)

Nội dung gốc

Lưu ý: Tài liệu này liên kết thẳng tới các phần liên quan trong danh mụ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 ý chính cần trình bày, các đánh đổi (tradeoff) và các phương án thay thế.

Thiết kế Bit.ly - là một câu hỏi tương tự, chỉ khác ở chỗ pastebin phải lưu nội dung đoạn paste thay vì lưu url gốc chưa rút gọn.

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õ, 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 (use cases)

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

• Người dùng nhập một khối văn bản và nhận về một đường link được sinh ngẫu nhiên
  • Thời hạn hết hạn (expiration)
    • Mặc định là không hết hạn
    • Có thể tùy chọn đặt thời gian hết hạn
• Người dùng nhập url của một đoạn paste và xem nội dung
• Người dùng là ẩn danh
• Dịch vụ theo dõi số liệu phân tích (analytics) của các trang
  • Thống kê lượt truy cập theo tháng
• Dịch vụ xóa các đoạn paste đã hết hạn
• Dịch vụ có tính sẵn sàng cao (high availability)

Ngoài phạm vi

• Người dùng đăng ký tài khoản
  • Người dùng xác minh email
• Người dùng đăng nhập vào tài khoản đã đăng ký
  • Người dùng chỉnh sửa tài liệu
• Người dùng có thể đặt chế độ hiển thị (công khai/riêng tư)
• Người dùng có thể tự đặt shortlink

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

Nêu các giả định

• Lưu lượng truy cập không phân bố đều
• Việc mở một short link phải nhanh
• Paste chỉ là văn bản
• Số liệu phân tích lượt xem trang không cần theo thời gian thực
• 10 triệu người dùng
• 10 triệu lượt ghi paste mỗi tháng
• 100 triệu lượt đọc paste mỗi tháng
• Tỷ lệ đọc/ghi là 10:1

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 làm các phép ước lượng nhanh (back-of-the-envelope) về mức sử dụng hay không.

• Kích thước mỗi paste
  • 1 KB nội dung mỗi paste
  • shortlink - 7 byte
  • expiration_length_in_minutes - 4 byte
  • created_at - 5 byte
  • paste_path - 255 byte
  • tổng = ~1,27 KB
• 12,7 GB nội dung paste mới mỗi tháng
  • 1,27 KB mỗi paste * 10 triệu paste mỗi tháng
  • ~450 GB nội dung paste mới trong 3 năm
  • 360 triệu shortlink trong 3 năm
  • Giả định phần lớn là paste mới chứ không phải cập nhật paste cũ
• Trung bình 4 lượt ghi paste mỗi giây
• Trung bình 40 yêu cầu đọc mỗi giây

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

• 2,5 triệu giây mỗi tháng
• 1 yêu cầu mỗi giây = 2,5 triệu yêu cầu mỗi tháng
• 40 yêu cầu mỗi giây = 100 triệu yêu cầu mỗi tháng
• 400 yêu cầu mỗi giây = 1 tỷ yêu cầu mỗi tháng

Bước 2: Tạo thiết kế tổng quan (high level design)

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

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 nhập một khối văn bản và nhận về một đường link được sinh ngẫu nhiên

Ta có thể dùng một cơ sở dữ liệu quan hệ (relational database) như một bảng băm (hash table) cỡ lớn, ánh xạ url được sinh ra tới một máy chủ tệp (file server) và đường dẫn chứa tệp paste.

Thay vì tự quản lý một file server, ta có thể dùng một kho lưu trữ đối tượng (Object Store) được quản lý sẵn như Amazon S3 hoặc một kho tài liệu NoSQL (document store).

Một phương án khác thay cho cơ sở dữ liệu quan hệ đóng vai trò bảng băm lớn là dùng một kho khóa-giá trị NoSQL (key-value store). Ta nên thảo luận các đánh đổi giữa việc chọn SQL hay NoSQL. Phần thảo luận dưới đây dùng cách tiếp cận cơ sở dữ liệu quan hệ.

• Client gửi yêu cầu tạo paste tới Web Server, đang chạy như một reverse proxy
• Web Server chuyển tiếp yêu cầu tới máy chủ Write API
• Máy chủ Write API thực hiện các việc sau:
  • Sinh một url duy nhất
    • Kiểm tra url có duy nhất không bằng cách tìm bản trùng trong SQL Database
    • Nếu url không duy nhất, sinh một url khác
    • Nếu hỗ trợ url tùy chỉnh, ta có thể dùng url do người dùng cung cấp (cũng phải kiểm tra trùng)
  • Lưu vào bảng pastes trong SQL Database
  • Lưu dữ liệu paste vào Object Store
  • Trả về url

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

Bảng pastes có thể có cấu trúc như sau:

shortlink char(7) NOT NULL
expiration_length_in_minutes int NOT NULL
created_at datetime NOT NULL
paste_path varchar(255) NOT NULL
PRIMARY KEY(shortlink)

Đặt khóa chính (primary key) dựa trên cột shortlink sẽ tạo ra một chỉ mục (index) mà cơ sở dữ liệu dùng để đảm bảo tính duy nhất. Ta sẽ tạo thêm một chỉ mục trên created_at để tăng tốc tra cứu (thời gian logarit thay vì quét toàn bộ bảng) và để giữ dữ liệu trong bộ nhớ. Đọ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.¹

Để sinh url duy nhất, ta có thể:

• Lấy giá trị băm MD5 của ip_address của người dùng + timestamp
  • MD5 là hàm băm được dùng rộng rãi, tạo ra giá trị băm 128 bit
  • MD5 phân bố đều
  • Ngoài ra, ta cũng có thể lấy MD5 của dữ liệu được sinh ngẫu nhiên
• Mã hóa Base 62 giá trị băm MD5
  • Base 62 mã hóa thành [a-zA-Z0-9], rất hợp với url vì không cần thoát (escape) ký tự đặc biệt
  • Mỗi đầu vào gốc chỉ có một kết quả băm, và Base 62 là tất định (deterministic - không có yếu tố ngẫu nhiên)
  • Base 64 là một cách mã hóa phổ biến khác nhưng gây rắc rối cho url vì có thêm ký tự + và /
  • Mã giả Base 62 sau chạy trong thời gian O(k), với k là số chữ số = 7:

def base_encode(num, base=62):
    digits = []
    while num > 0
      remainder = modulo(num, base)
      digits.push(remainder)
      num = divide(num, base)
    digits = digits.reverse

• Lấy 7 ký tự đầu của kết quả, cho ra 62^7 giá trị khả dĩ, đủ để đáp ứng ràng buộc 360 triệu shortlink trong 3 năm:

url = base_encode(md5(ip_address+timestamp))[:URL_LENGTH]

Ta sẽ dùng một REST API công khai:

$ curl -X POST --data '{ "expiration_length_in_minutes": "60", \
    "paste_contents": "Hello World!" }' https://pastebin.com/api/v1/paste

Phản hồi:

{
    "shortlink": "foobar"
}

Với giao tiếp nội bộ, 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 nhập url của một đoạn paste và xem nội dung

• Client gửi yêu cầu lấy paste tới Web Server
• Web Server chuyển tiếp yêu cầu tới máy chủ Read API
• Máy chủ Read API thực hiện các việc sau:
  • Kiểm tra url được sinh ra trong SQL Database
    • Nếu url có trong SQL Database, lấy nội dung paste từ Object Store
    • Ngược lại, trả về thông báo lỗi cho người dùng

REST API:

$ curl https://pastebin.com/api/v1/paste?shortlink=foobar

Phản hồi:

{
    "paste_contents": "Hello World"
    "created_at": "YYYY-MM-DD HH:MM:SS"
    "expiration_length_in_minutes": "60"
}

Trường hợp sử dụng: Dịch vụ theo dõi số liệu phân tích của các trang

Vì không yêu cầu phân tích theo thời gian thực, ta chỉ cần chạy MapReduce trên log của Web Server để tạo số đếm lượt truy cập (hit count).

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

class HitCounts(MRJob):

    def extract_url(self, line):
        """Trích url được sinh ra từ dòng log."""
        ...

    def extract_year_month(self, line):
        """Trả về phần năm và tháng của timestamp."""
        ...

    def mapper(self, _, line):
        """Phân tích từng dòng log, trích xuất và biến đổi các dòng liên quan.

        Phát ra các cặp khóa-giá trị có dạng:

        (2016-01, url0), 1
        (2016-01, url0), 1
        (2016-01, url1), 1
        """
        url = self.extract_url(line)
        period = self.extract_year_month(line)
        yield (period, url), 1

    def reducer(self, key, values):
        """Cộng dồn các giá trị theo từng khóa.

        (2016-01, url0), 2
        (2016-01, url1), 1
        """
        yield key, sum(values)

Trường hợp sử dụng: Dịch vụ xóa các đoạn paste đã hết hạn

Để xóa các paste đã hết hạn, ta chỉ cần quét SQL Database để tìm mọi bản ghi có timestamp hết hạn cũ hơn timestamp hiện tại. Tất cả bản ghi hết hạn sau đó sẽ bị xóa (hoặc đánh dấu là đã hết hạn) khỏi bảng.

Bước 4: Mở rộng thiết kế (scale the design)

Xác định và xử lý các nút thắt cổ chai (bottleneck), dựa trên các ràng buộc.

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õ rằng bạn sẽ làm theo vòng lặp: 1) Đo hiệu năng/Kiểm thử tải (Benchmark/Load Test), 2) Phân tích hiệu năng (Profile) để tìm nút thắt, 3) xử lý nút thắt đồng thời đánh giá các phương án thay thế và đánh đổi, và 4) lặp lại. Xem Thiết kế hệ thống mở rộng tới hàng triệu người dùng trên AWS làm ví dụ về cách mở rộng dần thiết kế ban đầu.

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

Ta sẽ bổ sung 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 load balancer nội bộ không được vẽ để sơ đồ đỡ 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 ý chính, đánh đổi và phương án thay thế:

• DNS
• CDN
• Load balancer
• Mở rộng theo chiều ngang (horizontal scaling)
• Web server (reverse proxy)
• API server (tầng ứng dụng - application layer)
• Cache
• Hệ quản trị cơ sở dữ liệu quan hệ (RDBMS)
• Chuyển đổi dự phòng (failover) cho SQL write master-slave
• Nhân bản master-slave (master-slave replication)
• Các mẫu nhất quán (consistency patterns)
• Các mẫu sẵn sàng (availability patterns)

Analytics Database có thể dùng một giải pháp kho dữ liệu (data warehouse) như Amazon Redshift hoặc Google BigQuery.

Một Object Store như Amazon S3 có thể thoải mái đáp ứng ràng buộc 12,7 GB nội dung mới mỗi tháng.

Để xử lý 40 yêu cầu đọc mỗi giây trung bình (cao hơn vào giờ cao điểm), lưu lượng cho nội dung phổ biến nên được phục vụ bởi Memory Cache thay vì cơ sở dữ liệu. Memory Cache cũng hữu ích để xử lý lưu lượng phân bố không đều và các đợt tăng đột biến. SQL Read Replicas sẽ đủ sức xử lý các lần trượt cache (cache miss), miễn là các bản sao không bị quá tải vì phải nhân bản các thao tác ghi.

4 lượt ghi paste mỗi giây trung bình (cao hơn vào giờ cao điểm) là khả thi với một SQL Write Master-Slave duy nhất. Nếu không, ta sẽ cần áp dụng thêm các mẫu mở rộng SQL:

• Liên kết (federation)
• Phân mảnh (sharding)
• Phi chuẩn hóa (denormalization)
• Tinh chỉnh SQL (SQL tuning)

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 ý bàn thêm (additional talking points)

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

NoSQL

• Kho khóa-giá trị (key-value store)
• Kho tài liệu (document store)
• Kho cột rộng (wide column store)
• Cơ sở dữ liệu đồ thị (graph database)
• SQL hay NoSQL

Bộ nhớ đệm (caching)

• Cache ở đâu
  • Cache phía client (client caching)
  • Cache tại CDN (CDN caching)
  • Cache tại web server (web server caching)
  • Cache tại cơ sở dữ liệu (database caching)
  • Cache tại tầng ứng dụng (application caching)
• Cache cái gì
  • Cache ở mức truy vấn cơ sở dữ liệu
  • Cache ở mức đối tượng
• Khi nào cập nhật cache
  • Cache-aside
  • Write-through
  • Write-behind (write-back)
  • Refresh ahead

Bất đồng bộ (asynchronism) và microservices

• Hàng đợi thông điệp (message queues)
• Hàng đợi tác vụ (task queues)
• Áp lực ngược (back pressure)
• Microservices

Giao tiếp (communications)

• Thảo luận các đánh đổi:
  • Giao tiếp bên ngoài với client - HTTP API theo REST
  • Giao tiếp nội bộ - RPC
• Khám phá dịch vụ (service discovery)

Bảo mật (security)

Tham khảo phần bảo mật.

Các con số độ trễ

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

Tiếp tục

• Tiếp tục đo hiệu năng và giám sát hệ thống để xử lý các nút thắt khi chúng xuất hiện
• Mở rộng quy mô là một quá trình lặp đi lặp lại