Bài toán Rate Limiter: Advanced Version

Rate Limiter là một bài toán cơ bản, phổ biến trong thiết kế hệ thống nhằm kiểm soát số lượng requests được thực hiện trong một khoảng thời gian nhất định, giúp cho hệ thống không bị quá tải một cách đột biến. OCG cũng đã implement một cơ chế Rate Limit ở tầng OpenResty cho ShopBase. Bạn hãy thiết kế và implement một cơ chế Rate limit với một số requirements sau:

Background

Storefront của các stores trên ShopBase rất hay bị crawl bởi nhiều thể loại bot như: Known bots (Google bot, Facebook bot, Bing bot)…hay các unkown bots (các bots nhiều bên bên tự implement để crawl dữ liệu). Thông thường, các known bot sẽ crawl theo những quy tắc nhất định như: 

• Tôn trọng thông tin trong file robots.txt
• Khi crawl thì thường theo dõi các HTTP Rate Limit header hay code HTTP 429 để điều chỉnh quá trình crawl của mình

Tuy vậy, các unknown bots lại không làm vậy dẫn đến hệ thống có thể sập do handle quá nhiều requests. 

Requirements

• Tính năng cơ bản: 
  • Xây dựng một Rate Limiter có khả năng kiểm soát số lượng requests dựa trên một số tiêu chí nhất định, chẳng hạn như số lượng requests mỗi giây, mỗi phút và mỗi ngày cho từng domain và IP nguồn.
    • Đơn vị thời gian tính toán lượng request có thể là 1s, 10s, 60s…
  • Phân loại được requests: Hỗ trợ việc phân loại requests theo loại, ví dụ: user-based rate limiting và API endpoint-based rate limiting.
    • User-based có thể là theo IP hoặc theo bot name, hoặc 1 identity nào đó truy cập vào hệ thống.
    • API endpoint-based tức là có thể set rate limit cho từng endpoint API dựa trên IP hoặc user.
      • VD: 
        • API login chỉ được access với limit 1 req/s/domain/ip
        • API get product có limit 100 req/s/domain/bot_name
  • Thiết kế mở rộng: Thiết kế hệ thống sao cho nó có khả năng mở rộng dễ dàng theo chiều ngang (nhiều máy cùng có thể chạy rate limit)
  • Quản lý trạng thái và logs: Ghi log cho mỗi request bị từ chối và duy trì thông tin về trạng thái của Rate Limiter.
    • Ví dụ: lúc đó, IP/user đã request bao nhiêu req trong 1 khoảng thời gian rồi, vì sao bị chặn truy cập
  • Code clean: Implement được codebase 1 cách clean nhất có thể và áp dụng được các design pattern cần thiết vào codebase.
• Chú ý:
  • Cần quyết định kiểu support đơn vị thời gian để thay đổi được 1 cách hợp lý.
    • Ví dụ đo theo 1s, 10s, 60s…
  • Mỗi stores có thể có nhiều domains, nên đơn vị để kiểm soát truy cập/limit là domain. 
    • Ví dụ:
      • Có thể set 20 requests/second/domain/src IP,  400 requests/minute/domain/src IP…
  • Nên có 1 hard limit cho toàn bộ hệ thống.
    • Ví dụ:
      • Khi tổng traffic vào hệ thống vượt quá ngưỡng 10000 request/s → các request sau đó sẽ bị rate limited

Gợi ý

• Để xử lý được bài toán này, bạn cần tìm hiểu các thuật toán rate limiter và chọn ra một thuật toán để có thể implements 1 cách đơn giản nhất.
  • Nếu bạn muốn thuật toán khó hơn hoặc cải tiến các thuật toán đang có, hãy cứ làm theo cách của bạn
• Đây là một bài toán về hiệu năng nên bạn nên viết sẵn các test cases, user stories để khi thiết kế/code không bị thiếu case nào
  • Cần có code/script test performance để bạn có thể tự test được. Ví dụ go test, wrk, apache bench, playwright…
• Bạn có thể sử dụng Golang hoặc Nodejs (prefer Golang) để thực hành
• Nên có thiết kế hệ thống rõ ràng trước khi bắt tay vào code
  • Nếu chưa chắc chắn, bạn hãy check với Lead hoặc @TruongBui

Output

1. 1 bản thiết kế hệ thống bao gồm:
   1. Tech docs theo format của OCG
      1. Giải thích được rõ ràng thiết kế của bạn trong đó
2. 1 user stories docs mô tả các user stories bạn sẽ giải quyết. Có thể theo format tại đây
3. Codebase trong gitlab của công ty, đặt trong tài khoản của bạn
   1. gitlab.shopbase.com/user_name/challenge_1
      1. Code base bao gồm code implement chức năng này và 1 HTTP server demo
      2. Thông tin đo đạc performance hệ thống lúc có và không áp dụng rate limiter
      3. 1 file README.md có các thông tin về những highlight của bạn về thiết kế, codebase
      4. Unit & Integration test
         1. Test Coverage > 60%
         2. Có code/script chạy test
            1. Xem hệ thống có chạy đúng rate limit theo config không

Thời hạn hoàn thành

Hết ngày 18/2/2024

Questions

Nếu có câu hỏi, hãy đừng ngần ngại chat vào channel #dev để được giải đáp

Reference

System Design Interview Volume 1 - Alex Xu