Hedged Request Memangkas Tail Latency dengan Duplikasi Terkendali

Sebuah service dapat memiliki median latency yang sehat sementara sebagian kecil request membutuhkan waktu jauh lebih lama. Queueing, garbage collection, storage stall, packet loss, noisy neighbor, atau load replica yang tidak merata dapat memperpanjang bagian lambat dari distribusi. Pada request yang melakukan fan-out ke beberapa dependency, satu cabang lambat dapat mendominasi waktu respons keseluruhan.

Hedged request mengurangi paparan tersebut dengan memulai salinan kedua setelah delay singkat. Kedua salinan diarahkan ke jalur eksekusi yang independen jika memungkinkan, lalu respons valid pertama yang selesai dipakai.

t=0 ms      kirim request ke replica A
t=25 ms     A masih pending; kirim duplikat ke replica B
t=39 ms     B merespons
            kembalikan respons B
            cancel atau abaikan A

Teknik ini sengaja bersifat selektif. Mengirim dua salinan untuk setiap request menggandakan offered work bahkan sebelum biaya cancellation dihitung. Hedge baru dimulai setelah request awal memakai bagian tertentu dari latency budget.

Hedge delay menentukan batas biaya

Hedge delay yang tetap sederhana diterapkan, tetapi nilainya perlu mencerminkan distribusi latency operasi yang diamati. Delay yang terlalu pendek membuat request normal menghasilkan duplikat. Delay yang terlalu panjang menyisakan terlalu sedikit waktu bagi salinan kedua untuk memperbaiki deadline caller.

Trigger berbasis percentile sering lebih stabil daripada konstanta arbitrer. Sebuah service dapat memulai hedge setelah recent p95 latency untuk kelas operasi yang sama, dengan batas minimum dan maksimum.

hedge_delay = clamp(recent_p95, 20 ms, 80 ms)

Percentile tersebut tidak harus presisi untuk setiap request. Nilainya menjadi policy yang mengikuti perubahan latency secara umum tanpa membuat duplikasi dimulai seketika.

Measurement window juga berpengaruh. Window yang sangat pendek dapat membuat threshold berosilasi mengikuti noise sesaat. Window yang terlalu panjang dapat mempertahankan threshold lama setelah workload atau infrastruktur berubah. Implementasi biasanya memisahkan latency telemetry dari request path dan memperbarui threshold ringkas secara periodik.

Independensi replica menentukan manfaat

Duplikat hanya membantu jika eksekusi kedua dapat menghindari kondisi yang menahan eksekusi pertama. Mengirim kedua salinan melalui queue, process, disk, atau downstream dependency yang sama-sama jenuh dapat menambah load tanpa memberi independensi yang berguna.

Replica selection karena itu penting. Hedge dapat memilih host, availability zone, connection, atau storage-shard replica yang berbeda, sesuai arsitektur dan consistency model.

client
  |
  +---- replica A ---- storage path 1
  |
  +---- replica B ---- storage path 2

Independensi jarang bersifat mutlak. Dua replica mungkin tetap berbagi network link, database primary, atau control plane. Hal yang relevan adalah apakah sumber dominan tail latency cukup tidak berkorelasi sehingga jalur kedua memiliki peluang berarti untuk selesai lebih cepat.

Cancellation diperlakukan sebagai optimasi

Setelah satu salinan menghasilkan respons valid, salinan yang kalah sebaiknya dibatalkan jika protocol dan server mendukung cancellation. Pembatalan dapat melepaskan queue slot, CPU time, connection capacity, dan downstream work.

Cancellation tidak dapat diasumsikan menghapus kerja yang sudah terjadi.

replica A: request diterima -> database query berjalan
replica B: respons selesai
client:    cancel A

Saat cancellation mencapai A, database query mungkin sudah selesai atau tidak mendukung interruption. Capacity planning karena itu harus memperhitungkan duplicate work yang benar-benar terjadi, bukan hanya duplikat yang masih terlihat di client.

Implementasi yang kuat juga menerima kemungkinan late response. Setelah operasi selesai di caller, hasil yang datang terlambat dari salinan lain dibuang tanpa mengubah outcome yang sudah final.

Operasi read merupakan titik awal yang paling aman

Hedging paling sederhana untuk read tanpa side effect. Dua eksekusi dapat berlomba tanpa membuat state transition ganda.

Write memerlukan semantik lebih ketat. Retry atau hedge pada write non-idempotent dapat membuat efek ganda jika kedua salinan mencapai commit point. Idempotency key dapat membuat submission berulang mengarah ke satu operasi logis, tetapi hanya jika setiap write path yang relevan menerapkan key tersebut secara atomik.

POST /payments
Idempotency-Key: 7f2c...

replica A ----\
               +--> durable idempotency record --> satu logical commit
replica B ----/

Key saja tidak cukup jika replica memakai deduplication state yang terpisah atau downstream effect melewati idempotency boundary. Untuk mutation path, hedging sebaiknya berada di belakang kontrak duplicate suppression yang sudah terbukti, bukan ditambahkan sebagai optimasi transport semata.

Aturan consistency tetap berlaku

Dua replica dapat mengembalikan versi data yang berbeda. Respons tercepat belum tentu merupakan respons yang dapat diterima.

Sistem strongly consistent mungkin mengharuskan kedua kandidat memenuhi read timestamp, leader epoch, fencing condition, atau quorum rule yang sama. Sistem bounded staleness dapat menolak replica cepat jika versinya berada di luar window yang diizinkan.

Mekanisme hedge memilih di antara respons yang sudah memenuhi correctness contract operasi. Mekanisme ini tidak boleh melonggarkan kontrak tersebut demi angka latency yang lebih kecil.

Perbedaan ini sangat penting selama failover. Replica yang baru dipromosikan dan replica yang tertinggal dapat memiliki response time serta posisi data yang berbeda. Routing policy memerlukan informasi versi yang cukup untuk menolak hasil cepat yang tidak valid.

Deadline membatasi window hedge yang berguna

Hedge harus mewarisi absolute deadline dari caller. Membuat duplikat tidak menciptakan waktu tambahan.

Misalnya sebuah request memiliki deadline 100 ms dan hedge delay 70 ms. Salinan kedua memiliki paling banyak 30 ms untuk selesai, dikurangi routing dan cancellation overhead. Jika replica tersebut biasanya membutuhkan 40 ms, hedge kecil kemungkinannya memberi hasil.

caller deadline: 100 ms

0 ---------------- 70 ---------------- 100
original berjalan   hedge dimulai        stop
                    <--- 30 ms --->

Policy dapat menahan hedge ketika remaining budget berada di bawah minimum yang dikonfigurasi. Dengan begitu, sistem tidak menambah kerja setelah peluang mendapatkan hasil yang berguna praktis sudah lewat.

Deadline propagation juga mencegah salinan yang kalah terus berjalan lama setelah caller meninggalkan operasi.

Concurrency limit mencegah hedging memperbesar overload

Tail latency sering naik saat overload, tepat ketika policy hedging yang naif akan membuat lebih banyak duplikat. Feedback loop tersebut dapat mengubah masalah latency menjadi masalah kapasitas.

Hedge memerlukan budget tersendiri. Kontrol yang berguna mencakup rasio maksimum hedged request, hedge concurrency limit per host, global token bucket, serta suppression ketika queue depth atau saturation melewati threshold.

if original_pending
   and remaining_budget >= min_useful_time
   and hedge_tokens.try_take()
   and target_has_capacity:
       send_hedge()

Hedge budget sebaiknya lebih kecil daripada budget request normal. Mekanisme ini merupakan kontrol tail latency, bukan jalur alternatif untuk retry tanpa batas.

Load shedding tetap memiliki prioritas. Ketika sistem sudah menolak work demi menjaga stabilitas, duplikasi spekulatif biasanya menjadi salah satu operasi opsional pertama yang dihentikan.

Retry dan hedge menangani waktu kegagalan yang berbeda

Retry biasanya dimulai setelah failure eksplisit, timeout, atau attempt ditolak. Hedge dimulai ketika attempt awal masih berjalan.

Perbedaan itu memengaruhi latency dan biaya. Menunggu timeout sebelum retry dapat menghabiskan sebagian besar deadline caller. Hedging memakai kapasitas tambahan lebih awal sebagai pertukaran untuk peluang selesai sebelum timeout tersebut.

Keduanya dapat digunakan bersama, tetapi budget perlu dikoordinasikan. Tiga retry dengan satu hedge pada masing-masing attempt dapat menghasilkan jauh lebih banyak eksekusi daripada perkiraan operator jika kedua policy dilihat secara terpisah.

Request policy sebaiknya menetapkan satu batas eksplisit untuk total attempt, termasuk original, hedge, dan retry.

Telemetry perlu memisahkan original dan duplikat

Aggregate latency saja dapat menyembunyikan biaya operasional hedging. Service memerlukan counter dan distribusi yang menunjukkan manfaat sekaligus kerja tambahan.

Measurement yang berguna mencakup hedge trigger rate, hedge win rate, cancellation success, runtime loser setelah winner selesai, attempts per logical request, p50/p95/p99 latency sebelum dan sesudah perubahan policy, serta resource utilization pada replica kandidat.

Trigger rate tinggi dengan win rate rendah sering menandakan threshold terlalu agresif atau delay antar-replica sangat berkorelasi. Win rate tinggi pun dapat terlalu mahal jika loser cancellation tidak efektif dan backend work memiliki biaya besar.

Unit utama adalah logical request. Attempt-level metric tetap berguna, tetapi tidak boleh menyamarkan seberapa banyak speculative work yang diperlukan untuk menyelesaikan satu operasi caller.

Tail latency turun karena policy, bukan sekadar duplikasi

Hedging efektif ketika attempt lambat merupakan outlier dan tersedia jalur eksekusi lain yang memenuhi syarat untuk selesai lebih cepat. Nilainya berkurang ketika kelambatan terjadi bersama di banyak replica, operasi terlalu mahal untuk diduplikasi, atau correctness rule mencegah perlombaan kandidat yang ekuivalen.

Desain praktisnya berupa policy yang dibatasi: tunggu cukup lama agar work normal tidak sering diduplikasi, pilih jalur eksekusi dengan independensi yang berguna, pertahankan correctness constraint yang sama, warisi deadline awal, cancel loser jika memungkinkan, dan hentikan spekulasi saat saturation.

Dengan batas tersebut, hedge bukan retry menyeluruh. Mekanisme ini memakai keragaman jalur eksekusi yang tersedia secara terkendali untuk mengurangi paparan terhadap jalur lambat yang jarang terjadi.