Giới thiệu

Giới hạn tốc độ là một cơ chế quan trọng giúp bảo vệ các dịch vụ khỏi việc bị quá tải bởi các yêu cầu từ một người dùng hoặc khách hàng. Bằng cách kiểm soát tốc độ của các yêu cầu đến, giới hạn tốc độ đảm bảo tính ổn định của hệ thống, ngăn chặn lạm dụng và duy trì sự công bằng trong việc sử dụng. Trong bài viết này, chúng ta sẽ khám phá năm thuật toán giới hạn tốc độ phổ biến nhất, thảo luận về ưu nhược điểm của chúng, cung cấp minh họa hình ảnh bằng các sơ đồ, và bao gồm các mẫu mã Python Django để thử nghiệm.

1. Thuật Toán Token Bucket

Cách thức hoạt động

• Hãy tưởng tượng một cái xô chứa các token với dung tích tối đa.
• Các token được thêm vào xô với một tỷ lệ cố định (ví dụ: 1 token mỗi giây).
• Khi một yêu cầu đến, nó phải tiêu thụ một token trước khi tiến hành. Nếu có token, yêu cầu được cho phép và token sẽ bị xóa.
• Nếu không có token, yêu cầu sẽ bị từ chối.

Ưu điểm

• Dễ dàng triển khai và hiểu.
• Hỗ trợ các đợt yêu cầu bùng nổ tối đa đến dung tích của xô, xử lý hiệu quả các đợt tăng đột biến lưu lượng ngắn hạn.

Nhược điểm

• Không đảm bảo một tốc độ hoàn toàn mượt mà.
• Sử dụng bộ nhớ tăng theo số lượng yêu cầu trên mỗi người dùng.

Triển khai Django

Dưới đây là mẫu mã Django triển khai thuật toán Token Bucket:

import time
from collections import deque
from django.http import HttpResponse
from django.views.decorators.http import require_GET

# Lưu trữ trong bộ nhớ cho Token Bucket (sử dụng Redis trong sản xuất)
token_buckets = {}

@require_GET
def token_bucket_limit(request):
    user_id = request.session.session_key or "anonymous"
    bucket_size = 10  # Số yêu cầu tối đa trong xô
    current_time = time.time()

    # Khởi tạo xô
    if user_id not in token_buckets:
        token_buckets[user_id] = {"tokens": bucket_size, "last_time": current_time}

    # Kiểm tra và thêm token
    elapsed = current_time - token_buckets[user_id]["last_time"]
    token_buckets[user_id]["tokens"] = min(bucket_size, token_buckets[user_id]["tokens"] + elapsed)
    token_buckets[user_id]["last_time"] = current_time

    # Xử lý yêu cầu
    if token_buckets[user_id]["tokens"] > 0:
        token_buckets[user_id]["tokens"] -= 1
        return HttpResponse("Yêu cầu được cho phép", status=200)
    return HttpResponse("Giới hạn tốc độ đã vượt quá", status=429)

Kiểm tra

Bạn có thể kiểm tra endpoint này tại /rate-limit/token-bucket. Nó xử lý tối đa 10 yêu cầu được xếp hàng.

2. Thuật Toán Leaky Bucket

Cách thức hoạt động

• Hãy tưởng tượng một cái xô với một lỗ nhỏ ở dưới cùng.
• Các yêu cầu vào xô từ trên.
• Xô xử lý các yêu cầu với tốc độ ổn định thông qua lỗ rò.
• Nếu xô đã đầy, các yêu cầu mới sẽ bị từ chối.

Ưu điểm

• Đảm bảo tốc độ xử lý ổn định và có thể dự đoán.
• Ngăn chặn các đợt bùng nổ đột ngột làm quá tải hệ thống.

Nhược điểm

• Hơi khó triển khai hơn so với Token Bucket.
• Xử lý kém trong trường hợp bùng nổ, các yêu cầu dư thừa sẽ bị từ chối ngay lập tức.

Triển khai Django

Dưới đây là mẫu mã Django triển khai thuật toán Leaky Bucket:

import time
from collections import deque
from django.http import HttpResponse
from django.views.decorators.http import require_GET

# Lưu trữ trong bộ nhớ cho Leaky Bucket (sử dụng Redis trong sản xuất)
leaky_buckets = {}

@require_GET
def leaky_bucket_limit(request):
    user_id = request.session.session_key or "anonymous"
    bucket_size = 10  # Số yêu cầu tối đa trong xô
    leak_rate = 1  # Yêu cầu mỗi giây
    current_time = time.time()

    # Khởi tạo xô
    if user_id not in leaky_buckets:
        leaky_buckets[user_id] = {"queue": deque(), "last_leak": current_time}

    # Rò rỉ yêu cầu
    elapsed = current_time - leaky_buckets[user_id]["last_leak"]
    leaks = int(elapsed * leak_rate)
    for _ in range(min(leaks, len(leaky_buckets[user_id]["queue"]))):
        leaky_buckets[user_id]["queue"].popleft()
    leaky_buckets[user_id]["last_leak"] = current_time

    # Thêm yêu cầu vào xô
    if len(leaky_buckets[user_id]["queue"]) < bucket_size:
        leaky_buckets[user_id]["queue"].append(current_time)
        return HttpResponse("Yêu cầu được cho phép", status=200)
    return HttpResponse("Giới hạn tốc độ đã vượt quá", status=429)

Kiểm tra

Bạn có thể kiểm tra endpoint này tại /rate-limit/leaky-bucket. Nó xử lý tối đa 10 yêu cầu được xếp hàng với tốc độ 1 yêu cầu mỗi giây.

3. Thuật Toán Fixed Window Counter

Cách thức hoạt động

• Thời gian được chia thành các khoảng cố định, ví dụ: khoảng 1 phút.
• Mỗi khoảng có một bộ đếm bắt đầu từ 0.
• Các yêu cầu đến sẽ làm tăng bộ đếm trong khoảng hiện tại. Nếu bộ đếm vượt quá giới hạn, yêu cầu sẽ bị từ chối cho đến khoảng tiếp theo.

Ưu điểm

• Dễ dàng triển khai và hiểu.
• Cung cấp giới hạn tốc độ rõ ràng cho mỗi khoảng.

Nhược điểm

• Gặp khó khăn với các đợt bùng nổ ở các ranh giới khoảng, có thể cho phép gấp đôi giới hạn tốc độ ở các cạnh.

Triển khai Django

Dưới đây là mẫu mã Django triển khai thuật toán Fixed Window Counter:

import time
from django.http import HttpResponse
from django.views.decorators.http import require_GET

# Lưu trữ trong bộ nhớ cho bộ đếm (sử dụng Redis trong sản xuất)
fixed_counters = {}

@require_GET
def fixed_window_limit(request):
    user_id = request.session.session_key or "anonymous"
    window_size = 60  # 60 giây
    max_requests = 10
    current_time = int(time.time())
    window_start = current_time - (current_time % window_size)

    # Khởi tạo hoặc đặt lại khoảng
    if user_id not in fixed_counters or fixed_counters[user_id]["window_start"] != window_start:
        fixed_counters[user_id] = {"window_start": window_start, "count": 0}

    # Kiểm tra và tăng bộ đếm
    if fixed_counters[user_id]["count"] < max_requests:
        fixed_counters[user_id]["count"] += 1
        return HttpResponse("Yêu cầu được cho phép", status=200)
    return HttpResponse("Giới hạn tốc độ đã vượt quá", status=429)

Kiểm tra

Bạn có thể kiểm tra endpoint này tại /rate-limit/fixed-window. Nó cho phép 10 yêu cầu trong khoảng 60 giây.

4. Thuật Toán Sliding Window Log

Cách thức hoạt động

• Một log lưu trữ các dấu thời gian cho mỗi yêu cầu.
• Khi một yêu cầu đến, các dấu thời gian cũ hơn kích thước khoảng sẽ được xóa.
• Số lượng dấu thời gian còn lại được đếm.
• Nếu số lượng nhỏ hơn giới hạn, yêu cầu sẽ được cho phép và dấu thời gian sẽ được thêm vào.
• Nếu số lượng vượt quá giới hạn, yêu cầu sẽ bị từ chối.

5. Thuật Toán Sliding Window Counter

Cách thức hoạt động

• Theo dõi số lượng yêu cầu cho các khoảng hiện tại và trước đó.
• Tính toán tổng trọng số dựa trên sự chồng chéo với khoảng trượt.
• Ví dụ, nếu 75% của khoảng hiện tại đã trôi qua, 25% trọng số đến từ khoảng trước đó và 75% từ khoảng hiện tại.
• Nếu tổng trọng số nhỏ hơn giới hạn, yêu cầu sẽ được cho phép.

Ưu điểm

• Chính xác hơn so với Fixed Window.
• Tiết kiệm bộ nhớ hơn so với Fixed Window Log.
• Làm mượt các ranh giới khoảng.

Nhược điểm

• Hơi phức tạp hơn để triển khai.

Triển khai Django

Dưới đây là mẫu mã Django triển khai thuật toán Sliding Window Counter:

import time
from django.http import HttpResponse
from django.views.decorators.http import require_GET

# Lưu trữ trong bộ nhớ cho bộ đếm (sử dụng Redis trong sản xuất)
sliding_counters = {}

@require_GET
def sliding_window_counter_limit(request):
    user_id = request.session.session_key or "anonymous"
    window_size = 60  # 60 giây
    max_requests = 10
    current_time = time.time()
    current_window = int(current_time / window_size) * window_size

    # Khởi tạo các bộ đếm
    if user_id not in sliding_counters:
        sliding_counters[user_id] = {"current_window": current_window, "current_count": 0, "previous_count": 0}

    # Cập nhật các khoảng
    if sliding_counters[user_id]["current_window"] != current_window:
        sliding_counters[user_id]["previous_count"] = sliding_counters[user_id]["current_count"]
        sliding_counters[user_id]["current_count"] = 0
        sliding_counters[user_id]["current_window"] = current_window

    # Tính toán tổng trọng số
    elapsed = current_time - current_window
    weight = elapsed / window_size
    weighted_count = sliding_counters[user_id]["previous_count"] * (1 - weight) + sliding_counters[user_id]["current_count"]

    # Kiểm tra và tăng
    if weighted_count < max_requests:
        sliding_counters[user_id]["current_count"] += 1
        return HttpResponse("Yêu cầu được cho phép", status=200)
    return HttpResponse("Giới hạn tốc độ đã vượt quá", status=429)

Kiểm tra

Bạn có thể kiểm tra endpoint này tại /rate-limit/sliding-window-counter. Nó cho phép 10 yêu cầu trong khoảng trượt 60 giây.

Thiết lập Dự Án Django

Để thử nghiệm các triển khai này, hãy thiết lập một dự án Django với các bước sau:

1. Tạo một dự án Django: django-admin startproject rate_limit_demo.
2. Tạo một ứng dụng: python manage.py startapp rate_limiter.
3. Thêm ứng dụng vào INSTALLED_APPS trong settings.py:

INSTALLED_APPS = [
    ...
    'rate_limiter',
]

4. Bật các phiên trong settings.py:

MIDDLEWARE = [
    ...
    'django.contrib.sessions.middleware.SessionMiddleware',
]

5. Thêm các view vào rate_limiter/views.py.
6. Cấu hình các URL trong rate_limiter/urls.py:

from django.urls import path
from . import views

urlpatterns = [
    path('token-bucket/', views.token_bucket_limit, name='token_bucket'),
    path('leaky-bucket/', views.leaky_bucket_limit, name='leaky_bucket'),
    path('fixed-window/', views.fixed_window_limit, name='fixed_window'),
    path('sliding-window-log/', views.sliding_window_log_limit, name='sliding_window_log'),
    path('sliding-window-counter/', views.sliding_window_counter_limit, name='sliding_window_counter'),
]

7. Bao gồm các URL của ứng dụng trong urls.py của dự án:

from django.contrib import admin
from django.urls import path, include

urlpatterns = [
    path('admin/', admin.site.urls),
    path('rate-limit/', include('rate_limiter.urls')),
]

8. Chạy máy chủ: python manage.py runserver.
9. Kiểm tra các endpoint bằng cách sử dụng curl hoặc trình duyệt (ví dụ: http://localhost:8000/rate-limit/token-bucket/).

Lưu ý: Các kho lưu trữ trong bộ nhớ (token_buckets, leaky_buckets, v.v.) chỉ dùng để minh họa. Trong sản xuất, hãy sử dụng Redis hoặc một cơ sở dữ liệu để duy trì trạng thái giữa các yêu cầu.

Lựa Chọn Thuật Toán Phù Hợp

Khi triển khai giới hạn tốc độ, hãy xem xét:

• Quy mô Hệ Thống: Các API có lưu lượng cao có thể yêu cầu các thuật toán tiết kiệm bộ nhớ như Token Bucket hoặc Sliding Window Counter.
• Mẫu Lưu Lượng: Lưu lượng bùng nổ được hưởng lợi từ Token Bucket, trong khi lưu lượng ổn định thích hợp với Leaky Bucket.
• Nhu Cầu Chi Tiết: Sliding Window Log cung cấp độ chính xác nhưng tiêu tốn bộ nhớ hơn.
• Thông báo giới hạn tốc độ một cách rõ ràng tới người dùng API thông qua các tiêu đề phản hồi (ví dụ: X-Rate-Limit-Remaining). Điều này giúp khách hàng thực hiện các chiến lược thử lại và lùi hợp lý.

Kết Luận

Giới hạn tốc độ là cần thiết để duy trì độ tin cậy và sự công bằng của dịch vụ. Năm thuật toán—Token Bucket, Leaky Bucket, Fixed Window Counter, Sliding Window Log, và Sliding Window Counter—cung cấp các giao dịch độc đáo trong đơn giản, độ chính xác và hiệu quả. Sử dụng các mẫu mã Django được cung cấp để thử nghiệm các thuật toán này và các sơ đồ để hình dung cơ chế của chúng.