Sliding window — thống kê trên cửa sổ trượt

TL;DR: Khi dữ liệu chảy mãi không dừng, bạn không giữ được cả lịch sử, chỉ giữ được "khung nhìn" N phần tử hoặc T giây gần nhất. Cửa sổ theo số phần tử (N mẫu gần nhất) trả lời max/min bằng monotonic deque, một hàng đợi hai đầu luôn xếp giảm dần, trung bình O(1) mỗi mẫu. Cửa sổ theo thời gian (T giây gần nhất) là nền của rate limiter: sliding log giữ hàng đợi timestamp nên chính xác nhưng tốn bộ nhớ theo số request, còn sliding window counter chỉ giữ hai bộ đếm của hai cửa sổ cố định liền kề, tốn O(1) nhưng ước lượng bằng nội suy nên có sai số. Chọn loại nào là chọn món bạn chịu mất: bộ nhớ hoặc độ chính xác.

Một API gateway giới hạn mỗi user 100 request trong 60 giây gần nhất. Giữ timestamp từng request: 100 × 8 byte = 800 byte mỗi user, 10 triệu user ra khoảng 8 GB (chưa tính overhead). Giữ hai bộ đếm: 2 × 8 byte × 10 triệu = 160 MB. Chênh 50 lần, cái giá là một phép ước lượng. Bài này đi từ cửa sổ theo số phần tử sang cửa sổ theo thời gian để thấy đánh đổi đó nảy ra từ đâu.

1. Cửa sổ theo số phần tử hay theo thời gian?

Hình dung bạn ngồi trên tàu nhìn qua khung cửa: chỉ thấy các cảnh gần nhất, cảnh mới vào mép phải thì cảnh cũ trôi khỏi mép trái.

Khung này đo được theo số phần tử ("độ trễ lớn nhất trong 1.000 mẫu gần nhất", khung cố định) hoặc theo thời gian ("số request trong 60 giây gần nhất", số phần tử trong khung lúc nhiều lúc ít). Cả hai dựa trên deque (hàng đợi hai đầu, thêm và bớt ở cả hai đầu đều tức thì), xem bài queue và deque.