Request Hedging cho Backend: Giảm tail latency mà không tạo bão tải

Một dịch vụ có median latency rất đẹp vẫn có thể mang lại trải nghiệm tệ nếu một tỷ lệ nhỏ request chậm bất thường. Trong kiến trúc fan-out, nơi một request người dùng phải chờ nhiều RPC con, chỉ một nhánh chậm cũng có thể kéo dài toàn bộ phản hồi. Request hedging xử lý phần đuôi này bằng cách gửi thêm một bản sao có kiểm soát sau một khoảng chờ; kết quả hợp lệ đầu tiên thắng và các bản còn lại bị hủy.

Kỹ thuật này nghe giống retry song song, nhưng mục tiêu và rủi ro khác retry thông thường. Hedge không đợi lần đầu báo lỗi. Nó đánh đổi một lượng tải bổ sung nhỏ để giảm xác suất phải chờ một outlier. Nếu dùng cho thao tác có side effect, đặt delay quá sớm hoặc không hủy công việc thua cuộc, hedge có thể nhân đôi giao dịch và biến latency spike thành bão tải. Bài viết trình bày cách xác định use case phù hợp, chọn ngưỡng từ dữ liệu, giữ một deadline chung, kiểm soát amplification và rollout an toàn.

1. Tail latency là vấn đề của phân phối, không phải số trung bình

Average hoặc p50 mô tả request điển hình nhưng che khuất phần đuôi. p99 là mức mà 99% request hoàn thành không chậm hơn giá trị đó; 1% còn lại có thể chậm hơn nhiều. Nguyên nhân có thể là pause của runtime, tranh chấp CPU, cache miss, connection mới, queue cục bộ, packet loss, replica đang compaction hoặc một dependency có đợt nhiễu ngắn.

Fan-out làm xác suất gặp đuôi tăng lên. Nếu một request tổng hợp cần tất cả 20 nhánh và mỗi nhánh độc lập có 1% khả năng rơi vào nhóm chậm, xác suất gặp ít nhất một nhánh chậm xấp xỉ 1 - 0.99^20, tức khoảng 18%. Đây chỉ là ví dụ xác suất để thấy hiệu ứng khuếch đại, không phải công thức capacity cho mọi hệ thống vì các nhánh thực tế có thể tương quan.

2. Request hedging hoạt động như thế nào?

Client gửi attempt đầu tiên đến một backend đủ điều kiện. Nếu chưa có kết quả sau hedge_delay, client gửi attempt thứ hai đến một backend khác. Khi một attempt trả kết quả hợp lệ, client hoàn tất logical request, hủy attempt còn chạy và không gửi các hedge đã lên lịch. Tất cả attempt phải dùng cùng request ID và cùng deadline tổng.

async function hedgedRead(request, deadline):
  first = send(request, chooseReplica(), deadline)
  timer = waitUntil(min(now + hedgeDelay, deadline))

  winner = await firstOf(first, timer)
  if winner is response:
    return winner

  second = send(request, chooseDifferentReplica(), deadline)
  response = await firstSuccessful(first, second, deadline)
  cancelAllExcept(response.attempt)
  return response.value

Đây là mô hình khái niệm. Code production còn phải phân loại response hợp lệ, xử lý hủy, đóng stream, truyền trace context, giới hạn số attempt và giải phóng tài nguyên trong mọi đường đi. “Khác replica” cũng phải được load balancer hỗ trợ; gửi hai lần đến cùng một queue nghẽn hiếm khi mang lại lợi ích.

3. Phân biệt hedge, retry và timeout

Timeout đặt giới hạn thời gian chờ. Retry tạo attempt mới sau khi attempt trước lỗi hoặc hết một timeout con. Hedge tạo attempt bổ sung khi attempt trước vẫn chưa kết thúc. Vì có thời gian chồng lấn, hedge có thể thắng một straggler nhanh hơn retry tuần tự nhưng cũng dùng đồng thời nhiều tài nguyên hơn.

Một logical request cần một policy rõ ràng thay vì chồng retry ở SDK, service mesh và application. Khi nhiều tầng tự tạo attempt, amplification tăng theo cấp số nhân và telemetry khó giải thích. Chọn một tầng chịu trách nhiệm, hoặc bảo đảm các tầng khác tắt retry/hedge cho cùng call path.

4. Chỉ hedge thao tác có semantics an toàn

Ứng viên tốt nhất là read-only request, deterministic query hoặc phép tính không tạo side effect. Ngay cả read cũng cần kiểm tra chi phí: một truy vấn report nặng gửi hai lần có thể gây hại hơn latency tiết kiệm được. Với write, không được suy luận rằng hủy HTTP/RPC nghĩa là server chưa thực thi; attempt thua có thể đã commit trước khi nhận tín hiệu hủy.

• An toàn tương đối: đọc object, tra metadata, truy vấn replica, tính toán thuần với input cố định.
• Cần cơ chế bổ sung: create order, charge payment, gửi email, enqueue job hoặc cấp phát tài nguyên.
• Không nên hedge: stream dài, payload lớn, thao tác giữ lock lâu, request khan hiếm quota hoặc dependency đã bão hòa.

Nếu nghiệp vụ buộc phải hedge một write, server cần idempotency key hoặc operation ID ổn định, lưu kết quả theo key và trả cùng kết quả cho các attempt trùng. Idempotency phải bao phủ side effect thực, không chỉ deduplicate ở gateway trong vài giây. Các attempt mang cùng key nhưng payload khác phải bị từ chối.

5. Hedge delay là quyết định quan trọng nhất

Gửi hai attempt ngay lập tức làm gần như gấp đôi tải và thường không phải cấu hình mặc định hợp lý. Delayed hedging chỉ gửi bản sao cho request đã đi vào vùng chậm. Một điểm bắt đầu thực dụng là percentile latency cao của từng method, chẳng hạn gần p95 hoặc p99 của attempt latency trong điều kiện khỏe, sau đó hiệu chỉnh bằng load test và SLO.

Delay phải theo method, vùng, kích thước payload và class traffic. Một ngưỡng chung cho mọi endpoint sẽ hedge quá nhiều call nặng hoặc quá muộn với call nhanh. Có thể dùng histogram trượt để thích nghi, nhưng cần min/max, tốc độ thay đổi giới hạn và fallback khi lượng mẫu ít. Không để một sự cố làm percentile tăng mãi khiến hedging vô hiệu đúng lúc cần thiết.

delay = clamp(
  healthyLatencyHistogram.percentile(0.95),
  minimumDelay,
  maximumDelay
)

if remainingDeadline <= delay + minimumUsefulWorkTime:
  doNotHedge()

Đo attempt latency tách khỏi logical-call latency. Nếu chỉ đo request cuối cùng, các attempt thua và bị hủy biến mất khỏi dữ liệu, khiến ngưỡng thích nghi trở nên thiên lệch.

6. Một deadline chung, không cấp thêm thời gian cho bản sao

Hedge không nên kéo dài deadline của người dùng. Nếu logical request có budget 300 ms và hedge bắt đầu ở 180 ms, attempt thứ hai chỉ còn tối đa 120 ms. Tạo deadline mới 300 ms cho bản sao biến một kỹ thuật giảm đuôi thành lý do giữ tài nguyên lâu hơn.

Deadline cần được truyền xuống dependency bằng cơ chế phù hợp và trừ chi phí network, serialization cùng thời gian để caller xử lý response. Backend nên kiểm tra budget còn lại trước công việc đắt đỏ. Một attempt đến quá muộn không còn khả năng hoàn tất nên bị từ chối sớm thay vì chiếm connection và CPU.

Hedge tạo thêm một con đường đến kết quả trong cùng time budget; nó không tạo thêm time budget.

7. Hủy nhanh attempt thua, nhưng không coi cancel là rollback

Sau khi có winner, client phải hủy attempt còn lại và bộ hẹn giờ chưa kích hoạt. Server cần phản ứng với cancellation ở các điểm có thể ngắt: trước khi lấy connection, giữa các batch tính toán, trước downstream call hoặc khi ghi response. Nếu thư viện chỉ ngừng chờ mà công việc phía server vẫn chạy, chi phí hedge tiếp tục tồn tại dù client đã thành công.

Cancellation là best effort. Request có thể hoàn tất trước khi tín hiệu đến, proxy có thể không truyền hủy, hoặc database query không hỗ trợ ngắt an toàn. Vì vậy capacity model phải tính cả “orphan work”. Với write, correctness vẫn phải dựa vào transaction, idempotency và trạng thái nghiệp vụ; không dựa vào cancel.

• Gắn cùng logical request ID cho tất cả attempt và một attempt ID riêng cho từng bản.
• Ghi nhận lý do kết thúc: success, application error, deadline, canceled-by-winner hoặc transport failure.
• Đo thời gian từ khi winner hoàn tất đến khi attempt thua thực sự dừng.
• Giới hạn response buffering để việc hủy không giữ payload lớn trong memory.

8. Kiểm soát load amplification bằng budget

Tỷ lệ hedge không được xem là hệ quả không giới hạn của latency. Đặt một hedge budget theo client, method hoặc cluster, ví dụ token bucket chỉ cho phép một phần nhỏ logical requests tạo attempt bổ sung. Budget có thể nạp theo số request thành công và cạn nhanh khi dependency lỗi, giúp tắt hedge trong sự cố kéo dài.

Cần trần cứng cho max_attempts; với đa số use case, chỉ một bản sao trễ đã đủ để đánh giá. Thêm hedge thứ ba hiếm khi miễn phí và làm reasoning khó hơn. Admission control phía server vẫn áp dụng bình thường: attempt hedge không được đặc quyền vượt concurrency limit. Khi nhận overload response hoặc server pushback, client phải ngừng tạo thêm attempt.

if !policy.allows(request.method):
  return singleAttempt()
if hedgeBudget.empty() or dependency.isOverloaded():
  return singleAttempt()
if globalInFlightHedges >= hardLimit:
  return singleAttempt()

hedgeBudget.consume(1)
return delayedHedge(maxAttempts = 2)

9. Chọn replica phải tránh correlated slowness

Hedge chỉ hiệu quả khi attempt thứ hai có cơ hội thoát nguyên nhân làm attempt đầu chậm. Nếu cả hai đi qua cùng connection, cùng backend process, cùng shard đang lock hoặc cùng availability zone có sự cố mạng, bản sao chỉ tăng tải. Load balancer nên loại endpoint của attempt đầu và vẫn tuân thủ locality, health, outlier detection cùng dữ liệu shard.

Không được gửi request đến replica không sở hữu dữ liệu hoặc có consistency yếu hơn contract. Với read replica, cần xác định độ trễ replication chấp nhận được. Nếu caller yêu cầu read-your-writes, một hedge sang replica stale có thể trả nhanh nhưng sai semantics. Latency optimization luôn đứng sau correctness.

Power-of-two choices, least-request hoặc queue-aware routing đôi khi giảm tail latency ngay từ đầu mà không cần hedge. Trước khi thêm speculative work, hãy sửa các vấn đề rõ ràng như connection pooling, hotspot, queue không giới hạn và load balancing thiếu thông tin.

10. Observability phải nối logical call với từng attempt

Một trace span duy nhất cho logical request là chưa đủ. Tạo child span cho từng attempt với endpoint, thời điểm bắt đầu, hedge delay, kết quả, cancellation và số budget còn lại. Metric cần phân biệt logical calls với physical attempts để dashboard không báo throughput nghiệp vụ tăng chỉ vì gửi bản sao.

• Logical latency p50/p95/p99 và deadline-miss rate.
• Attempt latency theo method, endpoint, zone và trạng thái cache.
• Hedge trigger rate, win rate và tỷ lệ attempt thua bị hủy thành công.
• Request amplification: physical attempts chia cho logical calls.
• CPU, connection pool, queue age và downstream QPS tăng thêm do hedge.
• Duplicate side-effect detection và idempotency conflict đối với write được bảo vệ.

Hedge win rate rất thấp có thể nghĩa delay quá muộn hoặc outlier không độc lập. Win rate cao nhưng amplification lớn có thể nghĩa delay quá sớm hoặc hệ thống gốc có vấn đề cần sửa. Mục tiêu không phải tối đa số hedge thắng, mà là giảm SLO miss với chi phí đo được và giới hạn.

11. Kiểm thử dưới tải và trong các failure mode thực tế

Benchmark không có contention thường làm hedging trông rất tốt. Hãy kiểm thử khi một replica có pause ngắn, một zone tăng network latency, cache miss, pool gần đầy và toàn cluster quá tải. So sánh baseline với nhiều delay và budget khác nhau. Đo cả p99 cải thiện lẫn CPU, QPS dependency, hàng đợi và tỷ lệ hủy.

1. Xác nhận chỉ method trong allowlist được hedge và max attempts không bị vượt.
2. Chứng minh mọi attempt dùng một deadline chung và cùng idempotency key khi cần.
3. Tiêm một straggler độc lập để kiểm tra bản sao chọn endpoint khác.
4. Làm cả cluster chậm để xác nhận budget, overload signal và admission control tắt hedge.
5. Cho winner xuất hiện sát thời điểm hedge để kiểm tra race và cleanup.
6. Ngắt client để chắc chắn server không giữ orphan work quá lâu.

Với write, test phải xác minh trạng thái bền vững chỉ xuất hiện một lần dù hai attempt cùng đến. Đếm response không đủ; cần kiểm tra database, event, message và tác động bên ngoài.

12. Quy trình rollout an toàn

1. Chọn một read method có volume vừa phải, tail latency rõ và backend có nhiều replica độc lập.
2. Thêm attempt-level telemetry và đo baseline trước khi bật hedge.
3. Chạy shadow calculation để biết bao nhiêu request sẽ được hedge ở từng delay nhưng chưa gửi bản sao.
4. Canary một tỷ lệ traffic nhỏ với max attempts bằng 2 và budget bảo thủ.
5. Đánh giá p99, deadline miss, amplification, saturation và chi phí trong cùng cửa sổ.
6. Mở rộng theo từng method; có kill switch và rollback cấu hình tức thời.
7. Rà soát policy sau thay đổi topology, load balancer hoặc latency profile.

Request hedging hữu ích nhất khi outlier hiếm, các replica có độ chậm tương đối độc lập và công việc có thể hủy hoặc deduplicate. Nó không chữa được thiếu capacity kéo dài, database hotspot hay queue mất kiểm soát. Một triển khai tốt biến một phần rất nhỏ request thành speculative work để bảo vệ phần đuôi; một triển khai thiếu budget chỉ nhân đôi áp lực đúng lúc hệ thống yếu nhất.

Nguồn tham khảo

• Google Research: The Tail at Scale
• gRPC Documentation: Request Hedging
• gRPC A6: Client Retries and Hedging Design
• Amazon Builders' Library: Timeouts, Retries and Backoff with Jitter