Rate Limiter

Rate limiter: Đặt giới hạn số lượng requests mà 1 service sẽ tiếp nhận.

1 client sử dụng API mà được cấu hình chỉ 500 requests/phút, nếu client request với tốc độ vượt qua giới hạn này, client sẽ bị block.

Why do we need rate limiter?

Nhìn chung, rate limiter đc sử dụng như 1 lớp bảo vệ trước các hình thức tấn công có biểu hiện tăng cao lượng truy cập, như DDOS hay brute-force encryption.

Ngoài ra, nó còn đc ứng dụng vào các use case sau:

How will we design a rate limiter?

  1. Requirements

  2. High-level design

  3. Detailed design

  4. Rate limiter algorithms

Requirements of Rate Limiter

Functional Requirements

Non-functional Requirements

Types of throttling

Where to place rate limiter

2 models for implementing a rate limiter

Vì rate limter sẽ được cài đặt với số lượng khổng lồ cùng với bộ đếm cho lưu lượng requests đi tới, ta có thể sử dụng database để lưu lại thông số cùng với thông tin của người dùng.

Building blocks we will use

Design of a Rate Limiter

High-level design

1 rate limiter có thể đc deploy như là 1 service riêng biệt tương tác với web server. Khi 1 request đi tới, nó sẽ đưa ra quyết định request đó được đi tiếp hay ko.

Rate limiter bao hàm các quy tắc được tuân thủ chặt chẽ, định nghĩa nên throttling limit cho mỗi operation. Dưới đây là 1 ví dụ về limiter rule từ Lyft:

domain: messaging
descriptors:
	- key: message_type
	- value: marketing
	- rate_limit:
		- unit: day
		- request_per_unit: 5

Detailed design

Trong phần này ta sẽ thảo luận về các components trọng yếu cấu tạo nên rate limiter:

Rate limiter components

Rule database: 1 database để chứa các rules. Mỗi rule xác định 1 số lượng giới hạn các requests được chấp nhận trong 1 khoảng thời gian.

Rule retriever: Là background process được chạy định kỳ để kiểm tra bất kỳ sự thay đổi nào của rules. Rule cache sẽ được cập nhật từ đó.

Throttle rules cache: Cache bao gồm các rules được xuất từ rule database. Bộ nhớ cache phục vụ các rate-limiter request nhanh hơn các bộ nhớ ổn định, giúp gia tăng hiệu năng cho hệ thống.

Decision-maker: Bộ phận chịu trách nhiệm đưa ra quyết định theo các rules trong bộ nhớ cache.

Client identifier builder: Bộ phận này generate ra các ID độc nhất cho request từ 1 client. Nó có thể là 1 địa chỉ remote IP, login ID, hay là giá trị tổng hợp từ nhiều attributes. ID được gen ra này sẽ đc coi là 1 khóa lưu trữ cho dữ liệu ng dùng trong key-value database. Thế nên nó sẽ được chuyển tới decision-maker cho các lựa chọn tiếp theo.

Trong trường hợp giới hạn cho trước bị vượt quá, APIs sẽ trả về HTTP code 429 Too many requests, rồi áp dụng 1 trong 2 chiến lược xử lý sau:

Request Processing

Khi một request đi tới, client identifier builder sẽ định danh nó và forward tới decision-maker. Decision-maker xác định service mà request này yêu cầu, rồi kiểm tra bộ nhớ cache để đối ứng số lượng requests cho phép và rules được thiết lập bởi service.

Nếu request không vượt quá giới hạn cho phép, nó sẽ forward tới request processor.

Race Condition

Trong trường hợp có lượng request đồng thời cao, hiện tượng race condition sẽ dễ xảy ra.

Race condition chủ yếu xuất hiện ở quá trình cập nhật counter của rate limiter. Khi counter được query, tăng số rồi cập nhật lại vào database, sẽ có thể có nhiều requests đi tới cùng một lúc, dẫn tới việc đếm bị sai lệch.

Để tránh vấn đề này, ta có thể sử dụng cơ chế locking, nhưng như thế sẽ phải chấp nhận nguy cơ nút thắt cổ chai và giảm hiệu năng.

1 cách khác ta có thể sử dụng đó là cơ chế set-then-get, nghĩa là ta sẽ cộng số đếm trước, rồi insert vô database, như thế sẽ đỡ hẳn 1 quá trình query, thu hẹp thời gian cập nhật xuống.

Ngoài ra, ta nên ưu tiên việc shard counter, scale tới nhiều bộ đếm để có thể xử lý lượng request đồng thời cao.

A rate-limiter should not be on the client's critical path

Giả sử 1 trường hợp thực tế với hàng triệu requests hit vô frontend server. Mỗi request sẽ gọi ra, cập nhật và đẩy số đếm vô database. Quá trình này sẽ gây nên độ trễ lớn trong bối cảnh phải xử lý 1 lượng request khổng lồ. Để tránh vấn đề này, ta nên chia workload thành phần xử lý online và offline.

Ban đầu, khi nhận 1 request đc gửi từ client, hệ thống sẽ tính bộ đếm tương ứng. Nếu nó ít hơn giới hạn cho phép, hệ thống sẽ chấp nhận request này. Ở phase thứ 2, hệ thống sẽ cập nhật bộ đếm và bộ nhớ cache offline. Ở 1 vài request, ta sẽ ko thấy thay đổi nào đáng kể, nhưng với hàng triệu requests, ta sẽ thấy được hiệu suất được cải thiện rõ ràng.

Rate Limiter Algorithms

Token bucket algorithm

Token bucket algorithm illustration

Thuật toán này sử dụng sự tương đồng giữa một sức chứa cho trước với 1 cái xô bucket. Bucket theo định kỳ được làm đầy bởi các tokens với tốc độ không đổi. 1 token có thể được coi là 1 gói tin với kích thước cụ thể. Thuật toán kiểm tra token trong bucket mỗi khi nhận 1 request.

Giả sử ta có một rate limit đã đc định nghĩa R và sức chứa của 1 bucket là C, flow của thuật toán sẽ như sau:

  1. Thuật toán thêm 1 token mới vào bucket mỗi 1/R giây.

  2. Thuật toán bỏ qua token mới nếu số lượng token trong bucket bằng với C.

  3. Nếu ta có N requests đi tới trong khi bucket có N tokens, các tokens sẽ được tiêu thụ, và requests được forward tới các services sau.

  4. Nếu ta có N requests đi tới trong khi bucket có số tokens ít hơn N, ta sẽ chỉ chấp nhật số requests theo số tokens hiện có trong bucket.

Essential parameters

Advantages

Disadvantages

The leaking bucket algorithm

Leaking bucket algorithm illustration

Đây là 1 biến thể của thuật toán token bucket. Thay vì sử dụng token, thuật toán sử dụng 1 bucket với sức chứa có hạn để chứa các requests đi tới

Ý tưởng của thuật toán là dựa theo hiện tượng nước bị nhỏ giọt khỏi 1 xô nước bị quá đầy theo tốc độ không đổi. Lượng requests có thể tới với tốc độ bất kỳ, nhưng sẽ được xử lý theo tốc độ bất biến với thứ tự FIFO

Essential parameters

Advantages

Disadvantages

Fixed window counter algorithm

Fixed window counter algorithm illustration

Thuật toán chia chia thời gian chạy thành các quãng liên tục (được gọi là windows) và gán bộ đếm cho từng quãng. Khi 1 window nhận 1 request, bộ đếm tương ứng sẽ tăng 1. Một khi bộ đếm đến giới hạn, rate limiter sẽ ngừng tiếp nhận requests trong quãng thời gian đó.

Essential parameters

Advantages

Disadvantages

Sliding window log algorithm

Sliding window log algorithm illustration

Thuật toán này theo dõi từng request đi đến. Khi 1 request tới nơi, thời điểm đó sẽ được lưu lại trong 1 hash map, như là 1 log. Logs này được sorted dựa theo timestamp của request, và số lượng requests được chấp thuận sẽ dựa vào kích cỡ cho phép của log cùng khoảng thời gian hợp lệ.

Essential parameters

Advantages

Disadvantages

Sliding window counter algorithm

Sliding window counter algorithm illustration

Khác với thuật toán sliding window log ở trên, thuật toán này không giới hạn số lượng requests dựa theo giới hạn thời gian. Thuật toán áp dụng cả fixed window counter lẫn sliding window log để khiến cho requests được xử lý trôi chảy hơn.

Essential Parameters

Advantages

Disadvantages

E.g

Trong sơ đồ dưới đây, ta có 88 requests ở window trc và 12 requests ở window hiện tại. Ta đã set rate limit ở mức 100 requests tối đa mỗi phút.

Tưởng tượng 1 sliding window đã trượt sang window hiện tại 15s. Tại phút 2:15, thêm 1 request được đi tới, và ta sẽ quyết định chấp nhận request này hay ko dựa trên công thức sau:

Rate = Rp * (time_frame - overlap_time) / time_frame + Rc

Tại đây, Rp là số lượng requests trong cửa sổ trước, 88. Rc là số lượng requests trong cửa sổ hiện tại, 12. Time frame sẽ là 60s (1 phút), và overlap time là 15s.

Rate = 88 * (60 - 15) / 60 + 12
     = 78

=> Rate < 100

Như vậy request sẽ được chấp nhận.

A comparison of rate-limiting algorithms

Ta sẽ so sánh các thuật toán dựa trên 2 tiêu chí sau đây:

Token bucket algorithm

Leaking bucket algorithm

Fixed window counter algorithm

Sliding window log algorithm

Sliding window counter algorithm