System Design Primer

Tiếng Việt

English

Tiếng Việt

English

Giao diện

Thiết kế tính năng xếp hạng doanh số theo danh mục của Amazon ​

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 nội dung. 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ế.

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 để trả lời các câu hỏi làm rõ, ta sẽ tự định nghĩa một số use case và ràng buộc.

Use case ​

Ta giới hạn bài toán ở use case sau ​

  • Service tính các sản phẩm bán chạy nhất trong tuần qua theo danh mục
  • User xem các sản phẩm bán chạy nhất trong tuần qua theo danh mục
  • Service có tính sẵn sàng cao

Ngoài phạm vi ​

  • Toàn bộ site thương mại điện tử
    • Chỉ thiết kế các thành phần phục vụ việc tính xếp hạng doanh số

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

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

  • Traffic không phân bố đồng đều
  • Một sản phẩm có thể thuộc nhiều danh mục
  • Sản phẩm không thể đổi danh mục
  • Không có danh mục con, tức là không có dạng foo/bar/baz
  • Kết quả phải được cập nhật mỗi giờ
    • Các sản phẩm bán chạy hơn có thể cần cập nhật thường xuyên hơn
  • 10 triệu sản phẩm
  • 1000 danh mục
  • 1 tỷ giao dịch mỗi tháng
  • 100 tỷ read request mỗi tháng
  • Tỷ lệ đọc so với ghi là 100:1

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

Làm rõ với người phỏng vấn xem có cần tính nhẩm mức sử dụng hay không.

  • Kích thước mỗi giao dịch:
    • created_at - 5 byte
    • product_id - 8 byte
    • category_id - 4 byte
    • seller_id - 8 byte
    • buyer_id - 8 byte
    • quantity - 4 byte
    • total_price - 5 byte
    • Tổng: ~40 byte
  • 40 GB dữ liệu giao dịch mới mỗi tháng
    • 40 byte mỗi giao dịch * 1 tỷ giao dịch mỗi tháng
    • 1,44 TB dữ liệu giao dịch mới trong 3 năm
    • Giả định phần lớn là giao dịch mới chứ không phải cập nhật giao dịch có sẵn
  • Trung bình 400 giao dịch mỗi giây
  • Trung bình 40.000 read request 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.

Ta có thể lưu các file log thô của server Sales API trên một Object Store được quản lý sẵn như Amazon S3, thay vì tự quản lý một hệ thống file phân tán.

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

Giả sử đây là một dòng log mẫu, phân tách bằng tab:

timestamp   product_id  category_id    qty     total_price   seller_id    buyer_id
t1          product1    category1      2       20.00         1            1
t2          product1    category2      2       20.00         2            2
t2          product1    category2      1       10.00         2            3
t3          product2    category1      3        7.00         3            4
t4          product3    category2      7        2.00         4            5
t5          product4    category1      1        5.00         5            6
...

Sales Rank Service có thể dùng MapReduce, lấy các file log của server Sales API làm đầu vào và ghi kết quả vào bảng tổng hợp sales_rank trong một SQL Database. Ta nên thảo luận về use case và đánh đổi khi chọn giữa SQL hoặc NoSQL.

Ta sẽ dùng MapReduce nhiều bước:

  • Bước 1 - Chuyển dữ liệu thành (category, product_id), sum(quantity)
  • Bước 2 - Thực hiện distributed sort
python
class SalesRanker(MRJob):

    def within_past_week(self, timestamp):
        """Return True if timestamp is within past week, False otherwise."""
        ...

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

        Emit key value pairs of the form:

        (category1, product1), 2
        (category2, product1), 2
        (category2, product1), 1
        (category1, product2), 3
        (category2, product3), 7
        (category1, product4), 1
        """
        timestamp, product_id, category_id, quantity, total_price, seller_id, \
            buyer_id = line.split('\t')
        if self.within_past_week(timestamp):
            yield (category_id, product_id), quantity

    def reducer(self, key, value):
        """Sum values for each key.

        (category1, product1), 2
        (category2, product1), 3
        (category1, product2), 3
        (category2, product3), 7
        (category1, product4), 1
        """
        yield key, sum(values)

    def mapper_sort(self, key, value):
        """Construct key to ensure proper sorting.

        Transform key and value to the form:

        (category1, 2), product1
        (category2, 3), product1
        (category1, 3), product2
        (category2, 7), product3
        (category1, 1), product4

        The shuffle/sort step of MapReduce will then do a
        distributed sort on the keys, resulting in:

        (category1, 1), product4
        (category1, 2), product1
        (category1, 3), product2
        (category2, 3), product1
        (category2, 7), product3
        """
        category_id, product_id = key
        quantity = value
        yield (category_id, quantity), product_id

    def reducer_identity(self, key, value):
        yield key, value

    def steps(self):
        """Run the map and reduce steps."""
        return [
            self.mr(mapper=self.mapper,
                    reducer=self.reducer),
            self.mr(mapper=self.mapper_sort,
                    reducer=self.reducer_identity),
        ]

Kết quả sẽ là danh sách đã sắp xếp dưới đây, ta có thể chèn vào bảng sales_rank:

(category1, 1), product4
(category1, 2), product1
(category1, 3), product2
(category2, 3), product1
(category2, 7), product3

Bảng sales_rank có thể có cấu trúc sau:

id int NOT NULL AUTO_INCREMENT
category_id int NOT NULL
total_sold int NOT NULL
product_id int NOT NULL
PRIMARY KEY(id)
FOREIGN KEY(category_id) REFERENCES Categories(id)
FOREIGN KEY(product_id) REFERENCES Products(id)

Ta sẽ tạo index trên id , category_id và product_id để tăng tốc truy vấn (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 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

  • Client gửi request tới Web Server, chạy như một reverse proxy
  • Web Server chuyển tiếp request tới server Read API
  • Server Read API đọc từ bảng sales_rank trong SQL Database

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

$ curl https://amazon.com/api/v1/popular?category_id=1234

Response:

{
    "id": "100",
    "category_id": "1234",
    "total_sold": "100000",
    "product_id": "50",
},
{
    "id": "53",
    "category_id": "1234",
    "total_sold": "90000",
    "product_id": "200",
},
{
    "id": "75",
    "category_id": "1234",
    "total_sold": "80000",
    "product_id": "3",
},

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

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 đã cho.

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ằng bạn sẽ 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, rồi 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 như một 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 những vấn đề gì? CDN? Master-Slave Replicas? Phương án thay thế và đánh đổi của mỗi lựa chọn là gì?

Ta sẽ thêm 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ẽ ra để tránh rối sơ đồ.

Để tránh lặp lại các phần 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 giải pháp data warehouse như Amazon Redshift hoặc Google BigQuery.

Ta có thể chỉ muốn lưu dữ liệu của một khoảng thời gian giới hạn trong database, còn phần còn lại lưu trong data warehouse hoặc trong một Object Store. Một Object Store như Amazon S3 xử lý thoải mái ràng buộc 40 GB nội dung mới mỗi tháng.

Để xử lý trung bình 40.000 read request mỗi giây (cao hơn vào giờ cao điểm), traffic của nội dung phổ biến (và xếp hạng doanh số của chúng) nên do Memory Cache đảm nhận thay vì database. Memory Cache cũng hữu ích để xử lý traffic phân bố không đều và các đợt traffic tăng đột biến. Với lượng đọc lớn như vậy, các SQL Read Replicas có thể không chịu nổi các cache miss. Nhiều khả năng ta cần dùng thêm các pattern mở rộng SQL.

Trung bình 400 lượt ghi mỗi giây (cao hơn vào giờ cao điểm) có thể là quá sức với một 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 khác.

Các pattern mở rộng SQL gồm:

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 để đào sâu, tùy theo 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.

Các con số về latency ​

Xem Các con số về latency mà lập trình viên nào cũng nên biết.

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