Giảm 74% độ trễ p99: Cơ chế Adaptive Hedged Requests xử lý các yêu cầu "lạc hậu" trong kiến trúc phân tán

Trong thập kỷ qua, việc quan sát các kiến trúc microservice quy mô lớn đã chỉ ra một mô hình lặp đi lặp lại: sự tích tụ của các yêu cầu chậm (stragglers) trong kiến trúc fan-out làm suy giảm độ trễ p99, trong khi bảng điều khiển (dashboard) của từng dịch vụ riêng lẻ vẫn hiển thị màu "xanh". Phần lớn các dịch vụ đám mây trông có vẻ khỏe mạnh khi p50 nhanh và p90 ở mức chấp nhận được, nhưng khi nhìn vào p99, mọi thứ bắt đầu trở nên tồi tệ.

Stragglers vs Failures

Stragglers và Failures: Hai vấn đề khác nhau

Một thất bại (failure) là một yêu cầu không hoàn thành. Một straggler là một yêu cầu hoàn thành nhưng chậm: có thể do sự tạm dừng thu gom rác (GC pause), phân vùng nóng (hot partition), hoặc một trục trặc nhỏ trong lập lịch kernel. Từ góc độ của người gọi, cả hai đều gây hại cho p99. Tuy nhiên, chúng cần các giải pháp cơ bản khác nhau.

Thử lại (retry) giải quyết các thất bại bằng cách gửi một yêu cầu khác vì yêu cầu đầu tiên chưa kết thúc. Nhưng nếu yêu cầu đầu tiên sẽ hoàn thành, chỉ chậm hơn bình thường gấp 10 lần, việc thử lại sẽ thêm một yêu cầu thứ hai vào một backend đang chịu áp lực. Backend giờ đây có hai yêu cầu đang chạy cho cùng một thao tác logic, và chính yêu cầu thử lại đó có thể trở thành một straggler, làm cho p99 tồi tệ hơn chứ không tốt hơn.

Công cụ đúng đắn cho stragglers là hedged request (yêu cầu phòng vệ): Gửi một bản sao lưu trong khi yêu cầu chính vẫn đang chạy và sử dụng yêu cầu nào phản hồi trước. Yêu cầu thua cuộc sẽ bị hủy bỏ. Bạn không đợi thất bại, bạn đang đua để vượt qua yêu cầu chậm.

Tại sao Stragglers tích tụ ở quy mô lớn

Tỷ lệ straggler riêng lẻ thường trông có vẻ không đáng kể: khoảng 1% phản hồi chậm cho mỗi dịch vụ. 1% là hoàn toàn ổn, cho đến khi bạn xem xét kiến trúc fan-out. Trong kiến trúc fan-out, một yêu cầu người dùng duy nhất chạm đến nhiều dịch vụ hạ nguồn. p99 của hệ thống không được xác định bởi bất kỳ dịch vụ nào, mà được xác định bởi dịch vụ chậm nhất trong số tất cả chúng.

Fan-out amplification

Với 10 cuộc gọi hạ nguồn ở tỷ lệ straggler 1%, khoảng 9,6% yêu cầu cấp cao nhất gặp phải straggler. Khi thực hiện 100 cuộc gọi hạ nguồn, 63% yêu cầu cấp cao nhất sẽ gặp straggler. Đa số các yêu cầu cấp cao nhất của bạn sẽ bị chậm trễ bởi ít nhất một straggler, ngay cả khi từng dịch vụ riêng lẻ trông hoàn toàn khỏe mạnh. Đây là lý do tối ưu hóa các dịch vụ riêng lẻ thường không cải thiện p99 ở cấp hệ thống.

Vấn đề khó khăn: Khi nào nên Hedge

Quá sớm sẽ lãng phí dung lượng. Quá muộn thì bạn sẽ nhận được rất ít lợi ích.

Ngưỡng tĩnh (static threshold), ví dụ 50 mili-giây, trông rất tuyệt trong bài kiểm tra hiệu năng với phân phối độ trễ cố định. Tuy nhiên, môi trường sản xuất thì khác. Độ trễ thay đổi theo tải, triển khai, tinh chỉnh GC và thời gian trong ngày. Một ngưỡng 50ms hoàn hảo lúc 3 giờ sáng trở nên quá bảo thủ vào giờ cao điểm. Phân phối dịch chuyển lên và bạn chấp nhận các phản hồi chậm mà lẽ ra bạn có thể hedge. Một ngưỡng 10ms hoạt động tốt vào giờ cao điểm lại trở nên quá hung hăng lúc 3 giờ sáng. Bạn đang hedge các yêu cầu bình thường và thêm tải không cần thiết.

Cần có một cơ chế học hỏi phân phối độ trễ từ lưu lượng trực tiếp và kích hoạt hedge tại đúng điểm trong phân phối bất kể nó nằm ở đâu.

Cơ chế thích ứng: DDSketch

Để hedge ở p90 của phân phối hiện tại thực tế, bạn cần ước lượng phân vị thời gian thực cho mỗi máy chủ đích, được cập nhật trên mọi yêu cầu hoàn thành, với bộ nhớ bị chặn và chi phí O(1).

DDSketch cung cấp chính xác giải pháp này. Nó là một bản phác thảo phân vị luồng (streaming quantile sketch) với đảm bảo sai số tương đối: phân vị trả về luôn nằm trong khoảng +/- 1% của giá trị thực. Điều này rất quan trọng vì các giải pháp thay thế như thuật toán t-digest sử dụng giới hạn sai số xếp hạng có thể không chính xác tùy ý ở các phần trăm cao, đúng khu vực chúng ta quan tâm cho độ trễ đuôi.

DDSketch ánh xạ các giá trị thành các nhóm (buckets) logarit: bucket_index = ceil(ln(value) / ln(gamma)) trong đó gamma = (1 + alpha) / (1 - alpha) và alpha là độ chính xác tương đối mong muốn. Thao tác thêm là O(1). Bộ nhớ là hằng số. Chi phí trên đường dẫn quan trọng khoảng 35 nano-giây cho mỗi yêu cầu, có thể bỏ qua cho bất kỳ cuộc gọi mạng nào.

Ngăn chặn khuếch đại tải

Mối lo ngại rõ ràng với hedging là trong thời gian ngừng hoạt động thực sự (tức là khi backend thực sự chậm, không chỉ thỉnh thoảng tạo ra stragglers), mọi yêu cầu đều vượt quá ngưỡng hedge. Nếu không có van an toàn, bạn sẽ hedge mọi thứ và tăng gấp đôi tải backend vào thời điểm tồi tệ nhất.

Giải pháp là ngân sách token bucket. Giới hạn tỷ lệ hedge ở một phần trăm có thể cấu hình của tổng lưu lượng, ví dụ 10%. Công thức sau nắm bắt tốc độ làm đầy thùng: refill rate = estimatedRPS x budgetPercent / 100

Trong hoạt động bình thường với tỷ lệ straggler 5%, ngân sách không bao giờ cạn. Hedge kích hoạt khi cần thiết. Trong thời gian ngừng hoạt động, mọi yêu cầu đều chậm. Tại 1000 yêu cầu mỗi giây (RPS) với ngân sách 10%, thùng chứa 100 token và sẽ cạn trong khoảng một giây trong điều kiện ngừng hoạt động hoàn toàn, tự động dừng hedge trước khi nó có thể tăng gấp đôi tải backend. Dịch vụ suy giảm một cách nhẹ nhàng thay vì xoáy vòng.

Thích ứng với các điều kiện thay đổi

Một DDSketch duy nhất tích lũy các quan sát vô thời hạn. Nếu backend chậm lại trong 10 phút rồi phục hồi, các quan sát chậm cũ vẫn còn trong bản phác thảo. Ngưỡng hedge giữ ở mức cao nhân tạo và tiếp tục kích hoạt hedge trên các yêu cầu không cần nó.

Giải pháp là một cửa sổ trượt (tumbling window), hai bản phác thảo xoay vòng ở một khoảng thời gian cố định (ví dụ 30 giây). Các truy vấn phân vị hợp nhất cả hai bản phác thảo. Vì cả hai bản phác thảo đều được hợp nhất trên mỗi truy vấn, cửa sổ quan sát hiệu quả kéo dài từ một đến hai khoảng thời gian xoay vòng, từ 30 đến 60 giây ở cài đặt mặc định, mang lại các ước tính ổn định hơn so với cửa sổ cắt cứng trong khi vẫn loại bỏ dữ liệu cũ.

DDSketch windowed rotation

Hedging suy luận LLM: TTFT so với TTFB

Adaptive hedging áp dụng tự nhiên cho suy luận LLM, nhưng với một sự khác biệt quan trọng so với các dịch vụ HTTP tiêu chuẩn. Những gì cấu thành một phản hồi chậm là khác nhau.

Đối với một microservice điển hình, độ trễ được đo từ yêu cầu đến phản hồi. Đối với một điểm cuối LLM luồng sử dụng chuyển khối phân đoạn hoặc SSE, các tiêu đề phản hồi HTTP đến gần như ngay lập tức, thường trong vòng 1-2 ms. Chi phí thực sự là Thời gian đến Token đầu tiên (TTFT - Time to First Token), tức là thời gian cho đến khi byte đầu tiên của nội dung được tạo thực sự đến. Độ trễ đó, được thúc đẩy bởi tính toán prefill, trạng thái bộ nhớ đệm KV-cache và độ sâu hàng đợi, là nơi stragglers ẩn nấp.

Một hedge transport được hiệu chuẩn dựa trên thời gian nhận tiêu đề sẽ nhận được tín hiệu sai hoàn toàn. Trong các bài kiểm tra hiệu năng, bản phác thảo học được ngưỡng khoảng 1,6 ms và kích hoạt một yêu cầu sao lưu trên hầu hết mọi cuộc gọi, 100% chi phí phụ, vì hầu hết mọi yêu cầu "trông có vẻ chậm" so với tiêu đề gần như tức thì. Hedge đang đua sai chỉ số.

Giải pháp rất đơn giản nhưng yêu cầu móc vào đường dẫn đọc nội dung phản hồi thay vì thời gian nhận tiêu đề. Hedge đo độ trễ tại byte nội dung đầu tiên, không phải tại thời gian nhận tiêu đề, cung cấp cho DDSketch tín hiệu chính xác cho các kiến trúc prefill tách rời nơi tiêu đề và token đầu tiên cách nhau hàng chục đến hàng trăm mili-giây.

Khi KHÔNG nên Hedge

Adaptive hedging không phù hợp cho mọi khối lượng công việc:

• Các yêu cầu không có tính idempotent: Hedging gửi các yêu cầu trùng lặp. Nếu thao tác có tác dụng phụ (ví dụ: ghi, tính phí, hoặc thay đổi trạng thái), bạn sẽ thực hiện nó hai lần. Chỉ nên hedge các thao tác idempotent hoặc đảm bảo backend của bạn xử lý việc loại bỏ trùng lặp.
• Dịch vụ backend đơn lẻ: Hedging đua một bản sao lưu với yêu cầu chính. Nếu cả hai đều đi đến cùng một phiên bản duy nhất, hedge thêm tải vào cùng một máy tính đã chậm.
• Backend bị giới hạn bởi CPU: Nếu backend chậm vì bị bão hòa tính toán, việc thêm yêu cầu hedge làm tình trạng bão hòa tồi tệ hơn.
• Dịch vụ lưu lượng rất thấp: DDSketch cần các quan sát để tạo ra các ước lượng phân vị chính xác. Tại tốc độ yêu cầu rất thấp (dưới 1 RPS), bản phác thảo có thể không có đủ dữ liệu để phân biệt straggler với phương sai bình thường.
• Dịch vụ sau giới hạn tốc độ chia sẻ: Nếu backend áp dụng giới hạn tốc độ toàn cầu, các yêu cầu hedge sẽ tiêu thụ hạn ngạch đó.

Kết quả Benchmark

Với năm mươi nghìn yêu cầu chống lại một backend được mô phỏng với độ trễ cơ sở lognormal và xác suất straggler năm phần trăm, kết quả cho thấy cơ chế thích ứng giảm p99 từ 65ms xuống 17,3ms — một mức giảm 74%.

Cơ chế này khớp với các ngưỡng tĩnh được tinh chỉnh thủ công tốt nhất mà không cần bất kỳ cấu hình thủ công nào và quan trọng là, vẫn giữ chính xác khi các phân phối dịch chuyển. Việc triển khai tham chiếu bhope/hedge trên GitHub cung cấp hỗ trợ HTTP và gRPC thả vào cho các dịch vụ Go.