D · Serving policy

Vì sao hàng đợi tăng mạnh khi gần hết capacity

Lý thuyết hàng đợi giải thích vì sao độ trễ chờ tăng vọt theo hàm mũ khi mức sử dụng tài nguyên cụm GPU tiến sát 100%.

LESSON ID queueing GROUP Kiến trúc Inference

1Định nghĩa

Phân tích hàng đợi (queueing theory) giúp kỹ sư hiểu và dự báo thời gian một request phải nằm chờ trước khi được scheduler đưa vào chạy trên GPU. Tổng độ trễ mà người dùng cảm nhận luôn bằng thời gian nằm chờ trong hàng đợi cộng với thời gian thực thi (prefill và decode).

Khi lưu lượng truy cập đến theo từng đợt ngẫu nhiên (bursts) và độ dài câu trả lời biến thiên lớn, hệ thống không thể chạy ở mức 100% công suất mà vẫn giữ độ trễ thấp: ngay khi mức tải vượt ngưỡng 75–85% năng lực phục vụ, hàng đợi sẽ phình to theo đường cong phi tuyến. Hiểu quy luật này là cơ sở để đặt ngưỡng cắt tải ở gateway và tính phần công suất dự phòng (headroom) khi lập bài toán chi phí.

Ví dụ đời thường: Quy luật hàng đợi giống hệt cảnh quầy thu ngân siêu thị vào chiều cuối tuần hoặc trạm thu phí cao tốc. Khi lượng khách chỉ khoảng một nửa công suất quầy, ai tới cũng được tính tiền gần như ngay lập tức; nhưng khi quầy đã bận tới 90–95% công suất, chỉ cần 2 khách mua giỏ hàng đầy ắp xuất hiện cùng lúc là dòng người xếp hàng phía sau sẽ nối dài gấp nhiều lần.

2Luồng

Sơ đồ luồng (4 bước)

Request đến theo traffic
Có steady load hoặc burst.
Chờ tài nguyên
Scheduler chưa thể chọn mọi request.
Được phục vụ
Compute và memory quyết định service time.
Hoàn tất hoặc quá hạn
Ảnh hưởng mục tiêu dịch vụ.

Mã Mermaid

flowchart TD
  step1["Request đến theo traffic"]
  step2["Chờ tài nguyên"]
  step3["Được phục vụ"]
  step4["Hoàn tất hoặc quá hạn"]
  step1 --> step2
  step2 --> step3
  step3 --> step4

3Giải pháp

Sweep arrival rate để tìm vùng đáp ứng latency. Bounded admission và tăng capacity đúng lúc giúp tránh queue runaway.

Little’s law là quan hệ trung bình trong điều kiện phù hợp; không dùng nó thay tail measurement hoặc áp máy móc khi system đang overload.

4Profiling

Queue wait theo offered load
Vẽ latency khi tăng tốc gửi; tìm điểm bắt đầu tăng mạnh.
SLO attainment
Đếm request đạt mục tiêu ở từng mức tải, không chỉ request hoàn tất.

Mẹo đo lường: ghim số liệu trên workload thật, ghi cả p50/p95/p99 thay vì chỉ trung bình, và luôn ghi lại điều kiện chạy (batch, cache, đồng thời, phần cứng) trước và sau khi tối ưu. Số đo thiếu điều kiện chạy thì không so sánh được.

5Ví dụ

Ví dụ Little’s law

Giả sử steady state nhận 20 request mỗi giây và mỗi request ở hệ thống trung bình 2 giây: trung bình có 40 request trong hệ thống, gồm đang chạy và đang chờ.

Burst ngắn

Average arrival cả phút thấp vẫn có thể tạo queue cao trong vài giây; cần đo theo cửa sổ ngắn.

6Thuật ngữ

Arrival rate: Số request đến mỗi đơn vị thời gian.
Service time: Thời gian tài nguyên dành để xử lý công việc, khác thời gian chờ.
Little’s law: Trong trạng thái ổn định, số công việc trung bình trong hệ thống bằng arrival rate nhân thời gian ở hệ thống trung bình.

Glossary (3)

Service Level Objective: Mục tiêu mức dịch vụ được chọn để xác định request nào đạt yêu cầu.
Runtime: Phần mềm quản lý việc thực thi, buffers và phụ thuộc giữa phép toán.
Latency: Thời gian chờ để nhận một kết quả hoặc một bước kết quả.

7Bài liên quan

Cổng tiếp nhận và kiểm soát yêu cầu Lập lịch tính toán theo từng bước sinh token Quản lý vòng đời các bản sao mô hình

8Nguồn

TensorRT-LLM: tích hợp engine với dịch vụ

9Bài lab

Queue giới hạn, deadline và admission control

Mô phỏng hệ thống · workload giả định

Sửa worker, queue limit, deadline; kiểm tra cân bằng admitted, rejected, completed và pending.

Kết quả mong đợiSo cùng burst traffic với nhận tất cả và kiểm soát tiếp nhận theo deadline/queue limit. Request đã nhận có thể hoàn tất, hết hạn hoặc còn pending; rejected chỉ nằm trong offered. Demo hủy công việc quá hạn và báo cả rejected/expired, tránh làm latency đẹp bằng cách bỏ request thất bại. Service duration biết trước là giả định mô phỏng, chưa phải estimator production.

Tải queue.py ↓

queue.pyPYTHON

from collections import deque

arrivals = [(0, 2), (0, 4), (0, 2), (0, 3), (0, 1), (1, 4), (1, 2)]
workers, queue_limit, deadline = 2, 2, 5
assert workers > 0 and queue_limit >= 0 and deadline > 0

def simulate(admission):
    queue, active = deque(), []
    counts = dict(offered=0, admitted=0, rejected=0, completed=0, expired=0)
    latencies, incoming, peak_queue = [], 0, 0
    horizon = arrivals[-1][0] + deadline + sum(service for _, service in arrivals) + 1
    for t in range(horizon):
        # Hủy cả job trong queue lẫn job đang chạy khi deadline đã hết.
        kept = deque()
        for job in queue:
            if t >= job["deadline"]: counts["expired"] += 1
            else: kept.append(job)
        queue = kept
        kept_active = []
        for job in active:
            if t >= job["deadline"]: counts["expired"] += 1
            else: kept_active.append(job)
        active = kept_active
        while incoming < len(arrivals) and arrivals[incoming][0] == t:
            arrival, service = arrivals[incoming]; incoming += 1; counts["offered"] += 1
            due = arrival + deadline
            free_at = [t + job["left"] for job in active] + [t]*(workers-len(active))
            for job in queue:
                worker = min(range(workers), key=lambda i: free_at[i])
                free_at[worker] += job["left"]
            predicted_finish = min(free_at) + service
            reject = admission and (len(queue)+len(active) >= workers+queue_limit or predicted_finish > due)
            if reject: counts["rejected"] += 1
            else:
                queue.append(dict(left=service, arrival=arrival, deadline=due))
                counts["admitted"] += 1
        while queue and len(active)<workers: active.append(queue.popleft())
        peak_queue = max(peak_queue, len(queue))
        if admission: assert len(queue) <= queue_limit
        kept_active = []
        for job in active:
            job["left"] -= 1
            if job["left"] == 0:
                assert t+1 <= job["deadline"]
                counts["completed"] += 1; latencies.append(t+1-job["arrival"])
            else: kept_active.append(job)
        active = kept_active
        if incoming == len(arrivals) and not queue and not active: break
    pending = len(queue)+len(active)
    assert counts["offered"] == counts["admitted"] + counts["rejected"]
    assert counts["admitted"] == counts["completed"] + counts["expired"] + pending
    return counts, pending, peak_queue, latencies

for admission in (False, True):
    counts, pending, peak, latencies = simulate(admission)
    print("\nPolicy:", "deadline + bounded admission" if admission else "accept all")
    print("counts:", counts, "pending:", pending, "peak waiting:", peak)
    print("completed latencies:", latencies)
    print("fraction offered completed on time:", counts["completed"]/counts["offered"])
print("PASS: offered = admitted + rejected; admitted = completed + expired + pending.")
# Admission dự báo FIFO theo service đã biết; production cần estimator và theo dõi sai số.

Python outputSẵn sàng.