System Design Primer

Tiếng Việt

English

Tiếng Việt

English

Giao diện

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

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. Xem nội dung được liên kết để biết các ý thảo luận chung, đánh đổi và 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 paste thay vì url gốc chưa rút gọn.

Bước 1: Xác định use case và ràng buộc ​

Thu thập yêu cầu và giới hạn phạm vi bài toán. Đặt câu hỏi để làm rõ use case và ràng buộc. Thảo luận các giả định.

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

Use case ​

Chúng ta giới hạn bài toán ở các use case sau ​

  • User nhập một đoạn văn bản và nhận về một liên kết được tạo ngẫu nhiên
    • Thời hạn hết hạn
      • Mặc định là không hết hạn
      • Có thể tuỳ chọn đặt thời hạn hết hạn
  • User nhập url của một paste và xem nội dung
  • User là ẩn danh
  • Service theo dõi analytics của các trang
    • Thống kê lượt truy cập theo tháng
  • Service xoá các paste đã hết hạn
  • Service có tính sẵn sàng cao

Ngoài phạm vi ​

  • User đăng ký tài khoản
    • User xác minh email
  • User đăng nhập vào tài khoản đã đăng ký
    • User chỉnh sửa tài liệu
  • User có thể đặt chế độ hiển thị
  • User có thể tự đặt shortlink

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

Nêu các giả định ​

  • Traffic không được phân bổ đồng đều
  • Truy cập một short link phải nhanh
  • Paste chỉ gồm văn bản
  • Analytics lượt xem trang không cần theo thời gian thực
  • 10 triệu user
  • 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 so với ghi là 10:1

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

Làm rõ với người phỏng vấn xem có nên tính toán ước lượng nhanh về mức sử dụng hay không.

  • Kích thước mỗi paste
    • 1 KB nội dung cho 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 request đọc mỗi giây

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

  • 2.5 triệu giây mỗi tháng
  • 1 request mỗi giây = 2.5 triệu request mỗi tháng
  • 40 request mỗi giây = 100 triệu request mỗi tháng
  • 400 request mỗi giây = 1 tỷ request mỗi tháng

Bước 2: Tạo thiết kế mức cao ​

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

Imgur

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

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

Use case: User nhập một đoạn văn bản và nhận về một liên kết được tạo ngẫu nhiên ​

Chúng ta có thể dùng relational database như một hash table lớn, ánh xạ url được tạo ra tới một file server và đường dẫn chứa file paste.

Thay vì tự quản lý file server, chúng ta có thể dùng một Object Store được quản lý sẵn như Amazon S3 hoặc một NoSQL document store.

Thay cho relational database đóng vai trò hash table lớn, chúng ta có thể dùng một NoSQL key-value store. Nên thảo luận về đánh đổi giữa việc chọn SQL hay NoSQL. Phần thảo luận dưới đây dùng hướng relational database.

  • Client gửi request tạo paste tới Web Server, chạy như một reverse proxy
  • Web Server chuyển tiếp request tới Write API server
  • Write API server thực hiện các việc sau:
    • Tạo 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, tạo một url khác
      • Nếu hỗ trợ url tuỳ chỉnh, có thể dùng url do user cung cấp (cũng phải kiểm tra bản trùng)
    • Lưu vào bảng pastes của SQL Database
    • Lưu dữ liệu paste vào Object Store
    • Trả về url

Làm rõ với người phỏng vấn xem bạn được kỳ vọng viết bao nhiêu code.

Bảng pastes có thể có cấu trúc 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 primary key dựa trên cột shortlink sẽ tạo ra một index mà database dùng để đảm bảo tính duy nhất. Chúng ta tạo thêm một index trên created_at để tăng tốc tra cứu (thời gian log 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 microsecond, trong khi đọc từ SSD chậm hơn 4 lần và đọc từ đĩa chậm hơn 80 lần.1

Để tạo url duy nhất, chúng ta có thể:

  • Lấy hash MD5 của ip_address + timestamp của user
    • MD5 là hàm băm được dùng rộng rãi, cho ra giá trị hash 128 bit
    • MD5 phân bố đồng đều
    • Hoặc có thể lấy hash MD5 của dữ liệu được tạo ngẫu nhiên
  • Mã hoá Base 62 hash MD5
    • Base 62 mã hoá ra [a-zA-Z0-9], rất hợp cho url vì không cần escape ký tự đặc biệt
    • Với một đầu vào gốc chỉ có một kết quả hash, và Base 62 mang tính xác định (không có yếu tố ngẫu nhiên)
    • Base 64 là một kiểu mã hoá phổ biến khác nhưng gây vấn đề cho url vì có thêm các ký tự + và /
    • Pseudocode Base 62 dưới đây chạy trong thời gian O(k), với k là số chữ số = 7:
python
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:
python
url = base_encode(md5(ip_address+timestamp))[:URL_LENGTH]

Chúng 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

Response:

{
    "shortlink": "foobar"
}

Với giao tiếp nội bộ, chúng ta có thể dùng Remote Procedure Call.

Use case: User nhập url của một paste và xem nội dung ​

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

REST API:

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

Response:

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

Use case: Service theo dõi analytics của các trang ​

Vì analytics thời gian thực không phải là yêu cầu, chúng ta có thể đơn giản dùng MapReduce trên log của Web Server để tạo số lượt truy cập.

Làm rõ với người phỏng vấn xem bạn được kỳ vọng viết bao nhiêu code.

python
class HitCounts(MRJob):

    def extract_url(self, line):
        """Extract the generated url from the log line."""
        ...

    def extract_year_month(self, line):
        """Return the year and month portions of the timestamp."""
        ...

    def mapper(self, _, line):
        """Parse each log line, extract and transform relevant lines.

        Emit key value pairs of the form:

        (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):
        """Sum values for each key.

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

Use case: Service xoá các paste đã hết hạn ​

Để xoá các paste hết hạn, chúng ta có thể 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ị xoá (hoặc đánh dấu là đã hết hạn) khỏi bảng.

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

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

Imgur

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õ bạn sẽ làm theo cách lặp: 1) Benchmark/Load Test, 2) Profile để tìm nút thắt cổ chai, 3) xử lý các nút thắt cổ chai trong khi cân nhắc các phương án thay thế và đánh đổi, và 4) lặp lại. Xem Design a system that scales to millions of users on AWS làm ví dụ về cách mở rộng thiết kế ban đầu theo từng vòng lặp.

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

Chúng 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 internal load balancer không được vẽ ra để sơ đồ đỡ rối.

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

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

Một Object Store như Amazon S3 có thể dễ dàng đáp ứng ràng buộc 12.7 GB nội dung mới mỗi tháng.

Để xử lý 40 request đọc trung bình mỗi giây (cao hơn vào giờ cao điểm), traffic của nội dung phổ biến nên do Memory Cache phục vụ thay vì database. Memory Cache cũng hữu ích để xử lý traffic phân bổ không đồng đều và các đợt tăng đột biến. SQL Read Replicas nên đủ sức xử lý các cache miss, miễn là các replica không bị quá tải vì phải sao chép các lượt ghi.

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

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

Các ý thảo luận thêm ​

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

NoSQL ​

Caching ​

Xử lý bất đồng bộ và microservices ​

Giao tiếp ​

Bảo mật ​

Xem phần bảo mật.

Latency numbers ​

Xem Latency numbers every programmer should know.

Liên tục ​

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