#4 - Những cái đuôi

Amazon ước tính rằng mỗi 100ms latency khiến họ mất 1% doanh thu.

---

Bài viết thuộc series 50 Days of System Design, một series về thiết kế hệ thống dành cho người đọc chậm và muốn hiểu sâu.

---

Long-tail latency

Long-tail latency là hiện tượng user thi thoảng gặp phải độ trễ cực lớn (tiếng Nôm là lag lòi mắt) khi sử dụng các ứng dụng hay website. Long-tail latency thường được đo bằng percentiles - bách vị phân. Percentiles là phương pháp cho biết có bao nhiêu phần trăm dữ liệu nhỏ hơn một mốc giá trị cụ thể. Ví dụ, bạn đo latency của 10 request gần nhất và sắp xếp kết quả tăng dần:

1, 2, 5, 5, 18, 25, 33, 46, 122, 1000 (ms)

trong ví dụ này:

• 50th percentiles hay còn gọi là p50 là 18ms, nghĩa là 50% user sẽ trải nghiệm độ trễ thấp hơn 18ms.

• p90 là 122ms, nghĩa là 90% user sẽ trải nghiệm độ trễ thấp hơn 122ms, 10% còn lại sẽ thấy độ trễ cao hơn 122ms.

Tail latency liên quan trực tiếp đến trải nghiệm người dùng. Amazon ước tính rằng mỗi 100ms latency khiến họ mất 1% doanh thu (doanh thu 2024 của Amazon là hơn $600B). Năm 2006, Google tính toán được rằng mỗi 0.5 giây latency tăng thêm ở trang tìm kiếm làm giảm 20% lưu lượng truy cập.

Người dùng Internet là những kẻ thiếu kiên nhẫn

Các công ty tôi từng làm đều thiết lập báo động cho chỉ số percentile của tail latency. Thí dụ ở Shopee, khi p99 > x00 (ms), báo động kích hoạt, đội on-call sẽ lập tức vào cuộc điều tra nguyên nhân bất kể ngày hay đêm, nắng hay mưa. Nhiều người đặt câu hỏi: sao phải cuống lên vậy, chẳng phải với p99 thì chỉ 1% số request bị chậm thôi sao?

Mọi chuyện phức tạp hơn thế, các hệ thống ngày nay thường bao gồm nhiều service khác nhau. Ví dụ, khi bạn vào google.com và tìm kiếm một từ khóa, bản chất bên dưới hàng trăm service cùng xử lý đồng thời từ khóa đó để xây dựng được trang kết quả.

Để xử lý request từ user, cần đồng thời gửi request tới nhiều service khác nhau

Giả sử, Google phụ thuộc vào 100 service để xây dựng được trang kết quả tìm kiếm; và p99 của mỗi service là 1s, nghĩa là 1% request có latency lớn hơn 1s. Do độ trễ của người dùng cuối phụ thuộc vào service trả về kết quả chậm nhất, xác suất để người dùng gặp phải latency lớn hơn 1s lên tới 63%. Nói cách khác, một biến động nhỏ của latency trên một service có thể ảnh hưởng đến một lượng lớn người dùng.

P(fast request) = P(latency <= 1s) = 99%

P(at least 1 slow) = 1 - P(fast request)^100 = 1 - 0.99^100 ~ 63%

Nguyên nhân

Hiện tượng long-tail latency xuất phát từ nhiều nguyên nhân, phần lớn liên quan đến các trục trặc ngẫu nhiên ở tầng infra, nơi mà lập trình viên ít có khả năng tác động trực tiếp:

1. tranh chấp tài nguyên
   - các datacenter thường chia sẻ bởi nhiều service khác nhau, chúng có thể tranh chấp các tài nguyên chung như CPU, băng thông bộ nhớ, network, file system.
   - các cronjob chạy ngầm có thể sử dụng nhiều tài nguyên và khiến hệ thống giật cục trong một khoảng thời gian ngắn.

2. garbage collection
   garbage collector (GC) có nhiệm vụ dọn dẹp bộ nhớ. Khi quá trình dọn dẹp bắt đầu, GC phải có truy cập độc quyền vào heap memory, điều này khiến các ứng dụng khác trên server phải tạm dừng hoạt động.

3. hardware bottleneck

Hedged request

Hedged request là một kỹ thuật được sử dụng phổ biến ở Google để hạn chế long-tail latency. Kỹ thuật này được Jeff Dean và Luiz Barroso công bố lần đầu vào 2013 trong paper The Tail at Scale, vì vậy tôi khá ngạc nhiên khi thấy ít có công ty nào khác áp dụng đầy đủ kỹ thuật này¹. Nếu công ty bạn có sử dụng Hedged request, hãy để lại comment nhé, có thể tôi đã sống trong cái giếng này quá lâu rồi.

A horizontal scaling server cluster

Ngày nay, các Web service thường được triển khai trên nhiều replica server để tăng throughput và duy trì tính sẵn sàng (availability). Ý tưởng của Hedged request rất đơn giản: gửi cùng 1 request tới nhiều replica server, và sử dụng kết quả từ replica server phản hồi sớm nhất. Cụ thể:

• đầu tiên, gửi 1 request tới replica server X và đợi một khoảng thời gian D (ms), nếu X vẫn chưa phản hồi thì tiếp tục gửi 1 request (hedged request) tới replica server Y khác.

• sau khi nhận được phản hồi đầu tiên từ X hoặc Y, hủy request còn lại.

• lặp lại quá trình này nếu cả X và Y đều không phản hồi sau khoảng thời gian 2*D.

Hedged request khác Retry ở chỗ: Retry gửi lại request khi mà request đầu tiên bị timeout, còn Hedged request sẽ chủ động gửi lại request sau 1 khoảng thời gian D ngắn hơn timeout rất nhiều.

Có 2 lưu ý quan trọng:

1. API cung cấp bởi các replica server phải có tính idempotent, nghĩa là cùng một request được gửi đi gửi lại nhiều lần sẽ luôn cho ra cùng một kết quả ban đầu. Ví dụ bạn gửi request để thanh toán cùng một order 10 lần, thẻ tín dụng của bạn chỉ bị trừ tiền một lần.

2. Phải chọn khoảng thời gian chờ D một cách phù hợp.

   • Nếu D quá nhỏ sẽ dẫn đến overload hệ thống, khi mà quá nhiều hedged request được gửi về dẫn đến hiện tượng Retry Storm².

   • Nếu D quá lớn sẽ làm giảm hiệu quả của Hedge request.

   Trên thực tế, Google đã từng gặp sự cố liên quan đến việc chọn giá trị thời gian chờ D quá nhỏ lẫn quá lớn.
   

   Giải pháp là chọn giá trị D một cách linh hoạt và bằng với giá trị p95 latency hiện tại³. Nói cách khác, ta chỉ gửi hedged request cho 5% request chậm nhất. Điều này đảm bảo lượng tải phát sinh từ hedged request được giới hạn trong khoảng 5% tổng số request, trong khi vẫn đảm bảo hiệu quả giảm thiểu long-tail latency.
   
   Thử nghiệm thực tế cho thấy, khi đọc 1000 key từ 100 server Google Bigtable⁴ với D = 10ms, p99.9 latency đã giảm từ 1800ms xuống còn vỏn vẹn 74ms trong khi chỉ tăng load cho hệ thống 2%. Wow!

Kết

Long-tail latency là một thách thức dai dẳng đối với các hệ thống phân tán lớn khi mà nguyên nhân thường đến từ các yếu tố ngoài tầm kiểm soát. Kỹ thuật Hedged request mặc dù không giải quyết triệt để được nguyên nhân nhưng có thể giảm thiểu tác động của long-tail latency tới trải nghiệm người dùng.

cure the disease not the symptom
cure the symptoms not the disease.

Paper The Tail at Scale không chỉ đề cập đến hedged request mà còn giới thiệu nhiều giải pháp thú vị khác, chẳng hạn như tied request và micro-partition. Tôi hy vọng sẽ có cơ hội để viết thêm về những giải pháp này trong tương lai.

Cheers, until next time!

1. Cả Envoy và gRPC đều support request hedging, nhưng đều khá thô sơ.

2. Hiện tượng retry storm xảy ra khi một server gặp sự cố và client liên tục retry khiến server gặp khó khăn trong việc phục hồi và làm vấn đề trở nên tồi tệ hơn.

3. Có nhiều thuật toán hiệu quả để tính được percentile của stream data theo thời gian thực như: DDSketch, TDigest.

4. Google Bigtable là NoSQL database cung cấp bởi Google Cloud.