Bạn có từng gặp trường hợp F5 liên tục một trang web, đột nhiên nhận được thông báo "Quá nhiều request, vui lòng thử lại sau"? Hay khi đang căng thẳng săn sale 12/12, trang S đột nhiên "lag" và hiện thông báo hãy chờ trong hàng đợi?

Đó chính là khi rate limiter đang làm việc - một thành phần rất quan trọng trong các hệ thống, hôm nay hãy cùng mình thảo luận thành phần này nhé.

Tại sao chúng ta cần đến rate limiter

Bảo vệ hệ thống khỏi quá tải: Khi có quá nhiều request đồng thời đổ vào server, hệ thống có thể bị quá tải và crash. Rate limiter có thể điều tiết các request, đảm bảo server chỉ xử lý trong khả năng của nó, giúp trải nghiệm của mọi người dùng được tốt như nhau. Và đồng thời cũng hạn chế được tấn công DDoS.

Kiểm soát chi phí hạ tầng, đặc biệt đối với các hệ thống sử dụng cloud. Rate limiter giúp kiểm soát lượng tài nguyên sử dụng, từ đó giữ chi phí trong tầm kiểm soát.

Một rate limiter thì cần những yêu cầu gì ?

• Khi một người dùng truy cập website / API quá số lượt cho phép, họ sẽ bị block.
• Hoạt động ổn định khi hệ thống scale, có thêm nhiều node.

Ta sẽ đi luôn vào yêu cầu cơ bản đầu tiên của rate limiter. Để giải quyết được vấn đề này, thực chất ta sẽ phải giải quyết 2 vấn đề con của nó:

• Ta cần cách thức để xác định người đang truy cập là ai - nếu như không phân biệt giữa những người đang sử dụng sản phẩm thì ta làm sao giới hạn họ được
• Giải thuật để giới hạn người dùng này, có nhiều giải thuật có thể áp dụng và mỗi giải thuật lại có những điểm mạnh yếu khác nhau.

Xác định người đang truy cập là ai.

Đối với nhiều hệ thống, họ chỉ cho phép user truy cập phần mềm sau khi đã đăng nhập thành công, hoặc sử dụng Api Key. Đối với trường hợp này thì chỉ cần sử dụng userId hoặc apiKey là xong.

Vậy đối với các trang web cho phép truy cập public thì sao ? Lấy ví dụ điển hình như Amazon chẳng hạn, nếu không có cơ chế xác định người dùng ẩn danh thì rất dễ bị các hệ thống scraping cào đến hết dữ liệu.

Trong trường hợp này, ta có thể nghĩ đến việc sử dụng IP Address của client là danh tính của người đang truy cập website. Vì IP Address có tính duy nhất trên toàn cầu nên giải pháp này nghe có vẻ khá hợp lý.

Tuy nhiên thì ở kiến trúc mạng hiện đại, các client truy cập mạng internet hầu như đều thông qua router của nhà mạng. Nó thường sẽ đi qua một vài thiết bị của nhà mạng trước khi chạm đến lõi của internet thế giới.

Điều này đồng nghĩa với việc trước khi gói tin của người dùng chạm vào internet, nó đã phải đi qua các chuyển đổi NAT (Network Address Translation). Khi này địa chỉ IP Address của gói tin không thực sự là của người dùng mà là của Router nhà mạng. Với sự bùng bổ của các thiết bị sử dụng mạng và số lượng giới hạn IP address v4, nhiều nhà mạng chọn giải pháp để nhiều user dùng chung một địa chỉ IP Address.

Ngoài ra thì nếu các user dùng chung một mạng công ty, bệnh viện và các nơi công cộng khác, xác suất trùng địa chỉ IP Address cũng rất cao.

Vậy nếu như chúng ta lựa chọn giải pháp này, nhiều user sẽ bị chặn một cách không chính xác.

Sử dụng IP Address kết hợp với nhiều thông tin khác

Ngoài địa chỉ IP Address, ta có thể thu thập thêm một số thông tin của client, ví dụ như trên browser:

• User-agent: Hệ điều hành, trình duyệt, phiên bản trình duyệt, phiên bản hệ điều hành
• WebRTC
• Ngôn ngữ, font chữ cài đặt trên thiết bị
• Kích thước màn hình
• Và vô số thông tin khác.

Bạn có thể tìm hiểu thêm về khái niệm Browser Fingerprint cho giải pháp này. Tuy nhiên cũng cần lưu ý rằng các thông số này hoàn toàn có thể bị fake bởi những người dùng thông minh 😉.

Tiếp theo chúng ta sẽ nghiên cứu một số giải thuật để giới hạn truy cập nhé.

Giải thuật giới hạn người dùng

Fixed window

Tư tưởng hoạt động chính của giải thuật:

• Chia thời gian thành nhiều khoảng nhỏ
• Trong mỗi khoảng nhỏ đó, chỉ nhận một số lượng request nhất định từ một user
• Nhiều hơn sẽ bị loại bỏ

Đây là một giải thuật khá dễ hiểu, dễ triển khai.

Tuy nhiên giải thuật này có thể dẫn đến trường hợp trong một khoảng thời gian, có nhiều request được xử lý nhiều hơn số lượng cho phép

Sliding window

Cách làm của giải thuật này sẽ xử lý nhược điểm của Fixed Window, đó là trong một khoảng thời gian, chỉ có một số lượng request nhất định được xử lý cho 1 user.

Cách hoạt động như sau:

• Thuật toán sẽ theo dõi timestamp của các request.
• Khi có một request mới, hệ thống sẽ loại bỏ tất cả các timestamp đã quá hạn (timestamp cũ hơn thời điểm bắt đầu của window hiện tại)
• Nếu số lượng bản ghi trong log vẫn nhỏ hơn hoặc bằng mức cho phép thì request được chấp nhận, còn nếu vượt quá thì sẽ bị từ chối.
• Sau đó, timestamp của request mới sẽ được thêm vào log.

Ngoài Sliding window thì token bucket cũng là một giải thuật rất phổ biến

Token bucket

Token bucket là một “thùng” có dung lượng xác định trước. Token sẽ được nạp vào bucket theo một tốc độ cố định theo chu kỳ (ví dụ: 1 token / phút). Khi bucket đầy, token mới sẽ không được thêm nữa.

Ví dụ trong hình trên, dung lượng bucket là 5. Bộ phận nạp sẽ thêm 1 token vào bucket mỗi phút. Khi bucket đầy, token dư sẽ bị bỏ đi.

Mỗi request sẽ tiêu thụ 1 token. Khi có request đến, ta sẽ kiểm tra trong bucket có đủ token hay không.

• Nếu còn đủ token, ta lấy ra 1 token cho mỗi request, và request đó được chấp nhận.
• Nếu không đủ token, request sẽ bị từ chối.

Ưu điểm lớn nhất của giải thuật này là sẽ cho phép burst một lượng traffic trong khoảng thời gian ngắn, sau đó các request sẽ được xử lý đều đặn dần dần.

Ngoài ra vẫn còn rất nhiều giải thuật khác nữa, tuy nhiên 3 giải thuật trên là những giải thuật phổ biến, giải quyết được phần lớn yêu cầu chức năng. Tùy thuộc vào bài toán cụ thể mà ta có sự lựa chọn phù hợp.

Thiết kế tổng quan

Sau khi đã xem xét những thành phần cơ bản, ta có một thiết kế tổng quan cho rate limiter như sau.

Nên lựa chọn kĩ thuật nào để lưu trữ counter cho rate limiter? Đây là loại dữ liệu cần truy cập nhanh (nếu không sẽ thêm latency cho các API) và trong hầu hết các trường hợp, với xác suất mất dữ liệu thấp sẽ không gây ảnh hưởng lớn. Vì vậy lưu trữ ở cache sẽ là lựa chọn lý tưởng.

Cách hoạt động sẽ như sau:

• Client gửi request đến server.
• Rate limiter lấy thông tin từ request và redis, kiểm tra xem có bị giới hạn không.
• Thỏa mãn => gửi request vào phần API xử lý nghiệp vụ + tăng counter / thêm log ở redis
• Nếu không thì loại bỏ.

Tuy nhiên khi số lượng concurrent request lớn dần, việc lưu trữ và cập nhật dữ liệu liên tục có thể gây ra race condition. Ta có những cách nào để xử lý ?

Fixed Window

const key = `${identifier}:${window}`;      
// Atomic increment and get
const currentCount = await this.redis.incr(key);
// Set expiration only on first request of the window
if (currentCount === 1) {
    const ttl = windowSize + 1;
    await this.redis.expire(key, ttl);
}
const isAllowed = currentCount <= this.maxRequests;

Mấu chốt xử lý của Fixed Window là sử dụng toán tử INCR, việc này tránh được race condition, tốc độ nhanh và tốn ít bộ nhớ.

Sliding Window

const windowStart = currentTime - windowSize;
const key = `${prefix}${userIdentifier}`;

const pipeline = this.redis.pipeline();
// Use Redis Sorted Set
// Remove expired entries (older than window start)
pipeline.zremrangebyscore(key, '-inf', windowStart);
// Count current requests in the window (AFTER cleanup)
pipeline.zcard(key);
// Add current request timestamp
pipeline.zadd(key, currentTime, `${currentTime}-${Math.random()}`);
// Expire after windowTime
pipeline.expire(key, windowTimeTTL);

const results = await pipeline.exec();
const currentCount = results[1][1];
const allowed = currentCount < this.maxRequests;

Sorted Set là kiểu dữ liệu rất phù hợp cho sliding window:

• Lưu trữ dữ liệu theo thứ tự, ở đây là timestamp
• Có thể loại bỏ các request cũ theo timestamp và thêm request mới

Và kết hợp với pipeline sẽ giúp ta xử lý được tất cả logic ở dạng atomic, tránh được race condition hiệu quả.

Token bucket

Triển khai giải thuật này với redis là một bài toán khá thú vị và phức tạp, mọi người có thể tìm hiểu thêm nhé.

Vậy khi scale thêm nhiều node thì sao ?

Việc scale Rate limiter theo chiều ngang có vẻ không quá phức tạp, nhưng cũng cần lưu ý vài điểm:

• Ban đầu có thể lưu trữ thông tin rate limit tại 1 redis instance, khi này thì ta hoàn toàn có thể lựa chọn giải thuật bất kì cho load balancer sẽ đều phù hợp.
• Khi cần nhiều redis instance hơn thì ta có thể lựa chọn sticky session để một request luôn hit vào một server, hoặc sử dụng shard key phù hợp cho cụm redis.
• Nếu Redis server bị crash thì sao? Chúng ta có 2 phương án:
• • Fail-Closed: loại bỏ toàn bộ request với status 503: Service Unavailable. Những hệ thống cần sự chắc chắn, khả năng kiểm soát tốt sẽ ưu tiên cách làm này.
  • Fail-Open: cho các request đi qua. Tuy nhiên với một thành phần quan trọng đứng đầu như rate limiter, việc thả lỏng như vậy có thể gây ra tăng tải hệ thống đột ngột quá mức => crash.

Summary

Rate limiter là một thành phần không quá khó hiểu nhưng đóng vai trò rất quan trọng trong các hệ thống lớn.

Mình để một số tài liệu tham khảo để mọi người có thể tìm hiểu sâu hơn chủ đề này nhé.

Hẹn gặp lại mọi người ở bài viết tiếp theo.

Tài liệu tham khảo:

• ByteByteGo | Technical Interview Prep
• Design a Distributed Rate Limiter | Hello Interview System Design in a Hurry

Credit:

• Tất cả animation của giải thuật là từ bài viết Medium của tác giả Raphael De Lio, https://medium.com/redis-with-raphael-de-lio