Bộ giới hạn 1 000/giây lặng lẽ cho qua 8 000 — bốn cách đếm và cái bẫy bộ đếm trong Verticle

Hình dung một bộ giới hạn tần suất như người gác cửa đếm khách vào quán. Nếu anh ta xoá sổ đúng đầu mỗi giờ, một đám căn khớp mối nối — trăm người lúc 12:59, trăm người nữa lúc 1:01 — lọt vào gấp đôi mà cuốn sổ vẫn ghi đẹp "trăm mỗi giờ". Và nếu quán thuê tám người gác, mỗi người một cuốn sổ riêng, thì quán đầy gấp tám lần hạn mức trong khi ai cũng thề mình đếm đúng. Giới hạn tần suất là một trong những thứ dễ viết sai mà không ai phát hiện, vì nó trông như đang chạy: có người bị chặn, log có 429, biểu đồ đẹp. Chỉ đến khi ai đó thật sự cố vượt qua nó thì mới lộ ra hạn mức thật cao gấp đôi, hoặc gấp tám, con số bạn khai.

Bài này viết bốn bộ đếm bằng tay trên event loop Vert.x — không thư viện — rồi đo cả ba thứ: độ chính xác, chi phí mỗi lần kiểm, và bộ nhớ mỗi khoá.

Bốn cách đếm

Cửa sổ cố định — đơn giản nhất. Đếm trong cửa sổ hiện tại, sang cửa sổ mới thì về 0.

public boolean choQua(long nay){
    if (nay - batDau >= cuaSoNs) { batDau = nay; dem = 0; }
    return dem++ < hanMuc;
}

Nhật ký trượt — giữ dấu thời gian của từng lượt, vứt những mốc đã ra khỏi cửa sổ.

public boolean choQua(long nay){
    long nguong = nay - cuaSoNs;
    while (!moc.isEmpty() && moc.peekFirst() <= nguong) moc.pollFirst();
    if (moc.size() >= hanMuc) return false;
    moc.addLast(nay); return true;
}

Đếm trượt xấp xỉ — giữ hai con số, cửa sổ trước và cửa sổ này, rồi nội suy tuyến tính theo phần đã trôi qua.

double tyLe = 1.0 - (double) troi / cuaSoNs;
double uocTinh = demTruoc * tyLe + demNay;
if (uocTinh >= hanMuc) return false;
demNay++; return true;

Xô token — xô nạp lại liên tục theo thời gian, mỗi lượt lấy một token.

token = Math.min(dungLuong, token + (nay - mocCu) * tocDoMoiNs);
mocCu = nay;
if (token < 1.0) return false;
token -= 1.0; return true;

Ranh giới cửa sổ: chỗ cửa sổ cố định vỡ

Kịch bản kinh điển: hạn mức 100 lượt/giây; kẻ gọi bắn 100 lượt ở mốc 0,95 s rồi 100 lượt nữa ở mốc 1,05 s. Hai chùm cách nhau 100 ms. Tôi chạy với đồng hồ giả lập nên số liệu là tất định:

Cửa sổ cố định cho qua gấp đôi hạn mức, và nó làm vậy một cách hoàn toàn hợp lệ theo đúng định nghĩa của chính nó — mỗi cửa sổ vẫn đúng 100. Vấn đề là "100 mỗi giây" mà người ta muốn nói tới là 100 trong mọi khoảng một giây, không phải trong những khoảng một giây do bạn chọn mốc bắt đầu.

Đây không phải chuyện lý thuyết. Kẻ nào muốn vắt kiệt hạn mức chỉ cần căn đúng ranh giới — mà với cửa sổ cố định kiểu theo đồng hồ (giây hiện tại), ranh giới đó công khai cho tất cả.

Hai bộ đếm còn lại vượt hạn mức nhẹ (6% và 10%) và cả hai đều đúng theo thiết kế: xấp xỉ thì chấp nhận sai số để đổi lấy hai biến thay vì một hàng đợi, còn xô token thì cố ý cho phép bùng — đó là tính năng, không phải lỗi. Bùng đúng bằng dung lượng xô, sau đó tốc độ trung bình trở lại đúng hạn mức.

Chi phí và bộ nhớ

3 triệu lượt kiểm, đã hâm nóng 300 000 lượt, có biến volatile hút kết quả để JIT không vứt vòng lặp đi:

Nhật ký trượt đắt gấp 2,7 lần về thời gian và 22 lần về bộ nhớ, vì nó phải giữ một long cho mỗi lượt trong cửa sổ. Với 10 000 khoá và hạn mức 100 thì đó là 29,7 MB chỉ để đếm — và con số này tỉ lệ thuận với hạn mức, nên hạn mức 10 000/giây sẽ thành gần 3 GB. Đó là lý do nhật ký trượt gần như không bao giờ được dùng cho hạn mức lớn, dù nó là bộ duy nhất chính xác tuyệt đối.

Nhưng trước khi bạn chọn theo bảng này, hãy xem con số quan trọng hơn.

Chi phí đó biến mất hoàn toàn khi đặt vào một request thật

Tôi gắn từng bộ đếm vào một route rồi bắn tải 100 kết nối:

/tran     (khong bo dem)  : 105 160 req/s | p50 0,9 ms | p99 2,5 ms
/co-dinh  (9,1 ns)        : 105 607 req/s | p50 0,9 ms | p99 2,1 ms
/nhat-ky  (24,2 ns)       : 105 351 req/s | p50 0,9 ms | p99 2,2 ms

Không có khác biệt nào đo được. Số học giải thích ngay: ở 105 000 req/s, mỗi request tốn khoảng 9 500 ns công sức hệ thống. Bộ đếm đắt nhất chiếm 24,2 ns trong số đó — 0,25%, nằm gọn dưới mức nhiễu giữa hai lần chạy.

Nên luật là: đừng chọn bộ đếm theo tốc độ, hãy chọn theo độ chính xác và bộ nhớ. Cái duy nhất trong bảng chi phí thật sự đáng cân nhắc là 2 967 B mỗi khoá, vì nó nhân với số khoá và không có gì che nó đi.

Cái bẫy riêng của Vert.x: bộ đếm nằm trong Verticle

Viết bộ đếm thành trường của Verticle là chuyện tự nhiên nhất trên đời — Vert.x giam mỗi Verticle vào một event loop, nên không cần khoá gì cả. Rồi bạn triển khai nhiều bản sao để dùng hết CPU.

Hạn mức khai là 1 000/giây. Đo lượt thật sự được cho qua:

Nhân đúng tuyến tính, vì mỗi bản sao có bộ đếm riêng của nó. Và không có tín hiệu nào báo cho bạn: log vẫn đầy 429, tỉ lệ chặn vẫn cao, mọi thứ trông như đang chạy. Chỉ có hạn mức thật là gấp tám.

Chỗ này đặc biệt dễ dính vì setInstances() thường được chỉnh sau, lúc tối ưu hiệu năng, bởi người không nhớ rằng có một bộ đếm nằm trong đó. Đổi một tham số hiệu năng và vô tình nới hạn mức bảo vệ lên tám lần là một kiểu hỏng rất khó lần ra.

Dùng chung một bộ đếm: gần như đúng, và hỏng theo kiểu tệ nhất

Cách sửa hiển nhiên là để một bộ đếm static cho mọi bản sao dùng chung. Tôi thử đúng như vậy, 8 bản sao, hạn mức 1 000/giây:

/chung-khong-khoa : cho qua 470/giay   | 312 498 ngoai le
/chung-co-khoa    : cho qua 1 000/giay | 0 ngoai le

Bản không khoá ném 312 498 ngoại lệ trong năm giây và cho qua có 470/giây — thấp hơn hạn mức. ArrayDeque bị tám event loop sửa cùng lúc thì hỏng cấu trúc bên trong, và mỗi lần hỏng là một ngoại lệ mà tôi bắt lại rồi coi như "chặn".

Chi tiết đáng sợ nhất nằm ở chỗ đó: nếu tôi không bọc try/catch, ngoại lệ sẽ chui ra khỏi handler, Vert.x trả 500, và triệu chứng của một cuộc đua dữ liệu sẽ hiện ra dưới dạng "thỉnh thoảng lỗi 500 không rõ nguyên nhân" — không ai nghĩ tới bộ giới hạn tần suất. Nó cũng không tái hiện được ở tải thấp, và biến mất ngay khi bạn hạ xuống một bản sao để gỡ lỗi.

Bản có synchronized cho ra đúng 1 000/giây. Và cái giá của nó, đo với hạn mức đặt vô hạn để không có 429 nào làm nhiễu:

/tran (khong bo dem)          : 101 394 req/s | p99 2,2 ms
/nhat-ky (rieng moi loop)     :  99 349 req/s | p99 2,6 ms
/chung-co-khoa-rong (co khoa) : 100 919 req/s | p99 2,3 ms

Không có khác biệt đo được. Điều này đi ngược lại lời khuyên "đừng bao giờ khoá trên event loop" — và lời khuyên đó vẫn đúng về nguyên tắc, chỉ là nó nói về việc giữ khoá lâu. Ở đây vùng tranh chấp là một thao tác 24 ns; tám event loop hiếm khi va vào nhau, và khi va thì chờ vài chục nano giây.

Ranh giới thực dụng: khoá quanh một thao tác nano giây thì miễn phí; khoá quanh bất cứ thứ gì đọc đĩa, gọi mạng, hay chờ một Future thì là thảm hoạ — đúng như phần health check chặn event loop ở phần 27 đã cho thấy.

Chọn cái nào

• Một tiến trình, hạn mức nhỏ, cần chính xác tuyệt đối → nhật ký trượt, nhớ nhân bộ nhớ với số khoá trước khi quyết.
• Hạn mức lớn hoặc nhiều khoá → xô token. 134 B mỗi khoá, cho phép bùng có kiểm soát, và cái bùng đó thường đúng ý bạn: khách thật hay đến theo chùm.
• Cần rẻ và chấp nhận sai vài phần trăm → đếm trượt xấp xỉ.
• Cửa sổ cố định thì chỉ dùng khi bạn thật sự không quan tâm việc hạn mức có thể bị vượt gấp đôi trong chốc lát.
• Nhiều bản sao → hoặc dùng chung một bộ đếm có khoá, hoặc chia hạn mức cho số bản sao. Chia thì đơn giản hơn nhưng sai khi tải rơi lệch: một bản sao bị dồn khách sẽ chặn oan trong khi các bản sao khác ngồi không.
• Nhiều tiến trình hoặc nhiều máy thì mọi thứ trên đây không đủ — cần một kho đếm chung (Redis chẳng hạn), và lúc đó bạn đổi một thao tác 24 ns lấy một lời gọi mạng, tức là quay lại đúng bài toán cân nhắc mà gateway ở phần 28 đã bàn.

Kiểm nhanh xem bộ giới hạn của bạn có bị nhân lên không — không cần dựng tải, chỉ cần đếm:

r.get("/kiem-han-muc").handler(c -> {
    boolean ok = boDem.choQua(System.nanoTime());
    (ok ? quaDuoc : biChan).incrementAndGet();
    c.response().setStatusCode(ok ? 200 : 429).end();
});

for i in $(seq 1 5000); do curl -s -o /dev/null localhost:8080/kiem-han-muc & done; wait
curl localhost:8080/so-lieu     # so cho qua co dung han muc khong?

Nếu con số cho qua bằng hạn mức nhân với setInstances() của bạn, bạn vừa tìm ra nó.

Mẫu số chung

Một bộ giới hạn tần suất chỉ mạnh bằng số chỗ đang đếm: đặt bộ đếm trong mỗi bản sao thì "1 000/giây" lặng lẽ thành 1 000 × số bản sao, mà không một lỗi nào báo, vì mỗi bộ đếm đều thành thật nằm trong hạn mức của riêng nó — một giới hạn được cưỡng chế ở N nơi độc lập là N giới hạn. Đây là cái bẫy chia-nhỏ-trạng-thái-dùng-chung nói chung: một cache trong bộ nhớ mỗi pod, một connection pool mỗi bản sao nối vào một CSDL chung (đúng con bug setInstances × pool), bất cứ "sổ đếm cục bộ" nào lẽ ra phải là một sự thật toàn cục. Lời giải là một thẩm quyền duy nhất (bộ đếm dùng chung, kèm cái giá điều phối) hoặc chia hạn mức cho số mảnh (kèm cái giá lệch tải); không có "cứ đếm cục bộ" nào miễn phí. Và cái hệ số nhân ấy nấp kỹ vì cái nút tạo ra nó (setInstances) thường được vặn về sau, bởi người đã quên rằng có một bộ đếm sống bên trong.

Điều thứ hai: "đúng" của một thuật toán đếm phụ thuộc vào mô hình cửa sổ bạn thật sự muốn. Cửa sổ cố định căn theo đồng hồ có một lỗ hổng không phải lỗi mà là hệ quả của định nghĩa: 100-mỗi-giây-đồng-hồ cho phép 200 vắt qua mối nối hai giây, vì "100/giây" gần như luôn có nghĩa "100 trong bất kỳ giây nào" — điều cửa sổ cố định không hứa. Nhật ký trượt mua sự chính xác bằng bộ nhớ, xô token mua cú bùng có kiểm soát — chọn đúng ngữ nghĩa bạn cần. Và đừng chọn theo tốc độ: 24 ns là 0,25% một request thật, chìm dưới nhiễu, nên con số đáng cân là bộ nhớ mỗi khoá (2 967 B × số khoá), không phải nano giây. Ngay cả câu "đừng bao giờ khoá trên event loop" thật ra nói về thời lượng giữ khoá — một vùng tới hạn nano giây thì miễn phí; giữ một cái khoá xuyên qua I/O mới là thứ giết bạn.

Phần sau bàn về thử lại và timeout — và đo xem ba tầng cùng thử lại ba lần thì hạ nguồn nhận bao nhiêu request.