🔬 BACOT — Sesi Deep Learning

📚 Topik: Algoritma Load Balancing & Health Check yang Benar

Kategori: Infra · Level: 2/3 (intermediate–advanced)

🎯 Tujuan Belajar

Setelah sesi ini, kamu bisa menjawab dengan alasan teknis — bukan selera:

1. Kapan pakai round robin vs least-request vs P2C vs consistent hashing vs EWMA.
2. Bedakan health check aktif vs passive (outlier detection) dan kenapa kamu butuh dua-duanya.
3. Kenapa "health check = GET / return 200" adalah bug, bukan fitur.
4. Kenapa satu pool health check bisa menjatuhkan seluruh cluster (cascading failure).
5. Bilang dengan yakin: "di sistem ini, saya sengaja tidak pakai load balancer health check aktif, dan ini alasannya."

🧠 Penjelasan Inti

Load balancer melakukan dua hal berbeda yang sering dicampur:

Keduanya punya blind spot berlawanan:

• Distribusi murni (round robin) buta terhadap kondisi host → kirim traffic ke host yang sedang GC pause 800ms.
• Health check murni (aktif) buta terhadap relevansi health check ke traffic nyata → host lolos /healthz tapi semua query DB-nya timeout.

Ini inti sesi: load balancing adalah control loop, bukan fungsi hash. Input = observability signal (latency, error, queue depth), output = pemilihan host. Kalau signal-nya buruk, algoritma terbaik pun jadi noise generator.

⚙️ Cara Kerja Internal

1. Keluarga algoritma dan asumsi tersembunyinya

Round robin / weighted RR

next = (last + 1) mod N

Asumsi implisit: biaya tiap request kira-kira sama, kapasitas host sama, latensi host sama.

Asumsi ini pecah kalau: request punya distribusi durasi heavy-tail (p99 100× p50), atau ada host yang "sama secara spesifikasi" tapi noisy neighbor di node yang sama.

Least connections / least requests

pick argmin(active_requests[i] / weight[i])

Lebih baik untuk request heterogen. Masalah: power of two choices — memilih min dari N sekaligus butuh lock/atomic read semua counter; min dari 2 hampir sama bagusnya dengan biaya jauh lebih murah.

P2C (Power of Two Choices) — pilihan default de-facto di Envoy, Linkerd, NGINX Plus, gRPC.

a = rand(N); b = rand(N)
pick min(load[a], load[b])

Kenapa penting: dengan random murni, max load ≈ O(log N / log log N). Dengan P2C, max load ≈ O(log log N). Untuk N=1000, random murni bisa menumpuk ~10× rata-rata; P2C ~2–3×. Ini hasil analisis klasik "balls into bins" (Azar et al., 1994) — bukan benchmark vendor.

P2C butuh definisi "load". Kalau load = jumlah request aktif, host yang pegang request lambat akan cepat "terlihat sibuk" dan traffic menjauh — bagus. Tapi kalau request-nya di-cache dan selesai dalam 200µs, counter hampir selalu 0 dan P2C degenerasi ke random. Load metric harus mencerminkan waktu, bukan count.

EWMA latency Skor = exponentially weighted moving average latency. Envoy punya LEAST_REQUEST + Slow Start + opsi selection_degraded; Linkerd secara default pakai P2C dengan EWMA latency — ini pilihan desain yang menarik: latency EWMA lebih tahan terhadap request count yang fluktuatif.

Kritik: EWMA latency bisa "mengunci" host cepat yang sudah kewalahan (self-fulfilling: host cepat tetap cepat sampai antrean meledak). Mitigasinya adalah komponen load, bukan murni latency.

Consistent hashing / ring hash / Maglev Untuk cache affinity dan stateful routing (session, shard DB, pub/sub partition). Kunci: minimal disruption saat N berubah.

• Ring hash klasik dengan vnode: saat satu node hilang, ~1/N key berpindah. Dengan vnode sedikit, distribusi timpang → vnode banyak = memory naik.
• Maglev hashing (Google, NSDI 2016): lookup table berukuran fixed (default 65537 di beberapa implementasi), setiap endpoint mengisi slot dengan preference list. Keuntungan: lookup O(1) dengan array, bukan binary search tree, dan disruption saat perubahan sangat kecil plus tabel hampir penuh terisi (high load factor) sehingga distribusi lebih rata. Trade-off: setiap perubahan endpoint memicu rebuild tabel penuh — untuk cluster besar yang sering scaling, ini CPU spike periodik.
• Ketiga (ring hash, maglev) di Envoy punya hash_policy dengan fallback ke LB lain bila host hasil hash tidak sehat — tanpa fallback, satu host mati = key-nya pindah permanen ke host lain (rebalancing storm).

Random — sering diremehkan, tapi untuk pool besar dengan request seragam, random hampir sama baiknya dengan RR dan stateless (tidak ada shared counter → tidak ada contention di data plane). Ini yang membuatnya pilihan yang benar untuk sidecar dengan core banyak.

2. Health check aktif — anatomi parameter

interval ──┬──> probe ──> [pass] ──> healthy
           │                │
           └──> timeout ─────┴──> [fail] ──> unhealthy_threshold tercapai? ──> eject

Parameter yang benar-benar mengubah perilaku:

Angka nyata, jangan asal: Envoy default interval 10s, unhealthy_threshold 2, healthy_threshold 2, timeout 1s. Artinya worst-case deteksi ≈ 20s sebelum host mati dianggap mati. Untuk SLA ketat, 20s itu selamanya — dan inilah alasan passive health check wajib ada, bukan opsional.

Aturan penting: timeout health check harus < timeout request normal, dan health check harus menempuh jalur yang sama dengan request nyata (lihat bagian miskonsepsi).

3. Passive health check / outlier detection — mekanisme nyata

Ambil Envoy sebagai referensi konkret (terverifikasi dari dokumentasi resmi, docs versi 1.41.0-dev):

• Algoritma ejeksi (dari dokumen "Outlier detection"): 1. Host ditandai outlier. 2. Cek apakah jumlah host ter-eject < max_ejection_percent (default 10%). Kalau sudah lewat → host TIDAK di-eject. 3. Eject selama base_ejection_time × jumlah kali eject beruntun, di-cap max_ejection_time. Default base_ejection_time = 30s, max_ejection_time = 300s (atau base, mana yang lebih besar). 4. Setelah waktu habis, host otomatis kembali — tanpa verifikasi. Kalau masih rusak, dia gagal lagi dan waktu eject berikutnya lebih panjang (backoff linear, bukan eksponensial). 5. Kalau active health check aktif, satu probe sukses langsung uneject host dan mereset counter (kecuali successful_active_health_check_uneject_host: false).

• Detection types (default): consecutive_5xx (default 5), consecutive_gateway_failure (502/503/504 + local errors, default 5), consecutive_local_origin_failure, success_rate (stdev-based, default success_rate_stdev_factor 1900 → 19.0, minimum 5 host & 100 request), failure_percentage (default threshold 85%, minimum 5 host & 50 request).

• Interval sweep: default 10s. Ejection inline untuk consecutive-*, interval-based untuk success rate.

Panic threshold — bagian yang paling sering dilewatkan:

Envoy membuang status kesehatan bila host sehat < healthy_panic_threshold (default 50%). Artinya: kalau 6 dari 10 host gagal health check, cluster masuk panic mode dan traffic dikirim ke semua host termasuk yang gagal. Ini bukan bug — ini mitigasi cascade failure: lbih baik mengirim traffic ke host yang mungkin rusak daripada mengembalikan 503 ke 100% user.

Set panic_threshold: 0 kalau kamu benar-benar lebih suka "no healthy upstream" daripada degradasi parsial. Itu pilihan sadar, bukan default.

Detail halus dari docs yang layak dicatat: "If your active health check is not validating data plane traffic then in situations where active health checking passes but the traffic is failing, the endpoint will be unejected prematurely." → kombinasi active+passive bisa saling merusak kalau health check tidak representatif. Ini bukan teori; ini penyebab flapping yang sulit didiagnosis.

4. Slow start / warm-up

Host baru butuh JIT warmup, connection pool fill, cache fill. Kalau langsung dapat beban penuh → latensi spike → passive check eject dia → dia makin dingin → siklus.

Solusi: ramp bobot secara linear dari 0/10% ke 100% selama N detik (Envoy slow_start window; NGINX slow_start; Kubernetes tidak punya native-nya, harus via EndpointSlice weight atau proxy).

Ini wajib untuk runtime dengan JIT (JVM, .NET) atau aplikasi dengan lazy init besar.

5. Kenapa "health check yang benar" = satu topik terpisah

Kesalahan fundamental: health endpoint mengecek sesuatu yang tidak pernah gagal dalam produksi.

❌ GET /healthz → 200 OK        (server process hidup — selalu 200 selama binary jalan)
✅ GET /healthz → cek dependency yang benar-benar dipakai request path

Tapi jangan juga mengecek semuanya:

❌ /healthz → SELECT 1 ke DB primary + cek Redis + cek Kafka + cek S3

Ini menciptakan coupled failure domain: DB down → semua 50 instance dianggap unhealthy → LB kosong → 100% outage, padahal sebagian traffic masih bisa dilayani (read dari cache, atau write ke DB replica).

Pola yang benar: pisahkan tiga endpoint.

K8s secara eksplisit memisahkan ini: livenessProbe gagal → kubelet restart container; readinessProbe gagal → alamat pod dihapus dari EndpointSlice, container tidak disentuh; startupProbe sukses sekali → berhenti dan menyerahkan ke dua lainnya (sumber: dokumentasi resmi Kubernetes "Configure Liveness, Readiness and Startup Probes").

Konsekuensi yang sering dilupakan: liveness probe yang mengecek DB = restart storm. DB down 30 detik → semua pod di-restart bersamaan → cold start → database dihantam connection storm → down lebih lama.

🏗️ Diagram / Pseudocode

Control loop lengkap

                 ┌─────────────────────────────────────┐
   request ─────►│  LB                                    │
                 │  1. filter: healthy set                │
                 │  2. panic? → semua host                │
                 │  3. pick: P2C / EWMA / ring / RR       │
                 │  4. slow-start weight ramp             │
                 └───────┬──────────────────┬────────────┘
                         │                  │
              ┌──────────▼─────┐    ┌───────▼──────────┐
              │ active probe    │    │ passive observer │
              │ (periodic)      │    │ (per response)   │
              │ interval 10s    │    │ 5xx, timeout,    │
              │ unhealthy=2     │    │ reset            │
              └──────────┬─────┘    └───────┬──────────┘
                         │                  │
                    ┌────▼──────────────────▼────┐
                    │ health state per endpoint  │
                    │ + ejection backoff         │
                    │ + max_ejection_percent 10% │
                    └────────────────────────────┘

P2C dengan bobot dan slow start (pseudocode)

def pick(endpoints):
    healthy = [e for e in endpoints if e.health == HEALTHY]
    if len(healthy) < panic_threshold * len(endpoints):
        healthy = endpoints                      # panic mode

    a, b = random.sample(healthy, 2)
    return min(a, b, key=lambda e: e.load / e.effective_weight())

def effective_weight(e):
    if e.age < SLOW_START_WINDOW:
        return e.weight * (e.age / SLOW_START_WINDOW)
    return e.weight

e.load harus bukan sekadar jumlah request aktif kalau durasi request bervariasi. Minimal: outstanding_requests. Lebih baik: EWMA(latency) × outstanding (ini dia "load" versi Linkerd/Envoy-ish) — karena host dengan 5 request lambat lebih sibuk dari host dengan 50 request cepat.

Health endpoint yang tidak menciptakan coupled failure

# readyz: dependency critical-only, dengan cache agar tidak hammer DB
@app.get("/readyz")
def readyz():
    if not app.initialized:
        return 503, "not initialized"
    if time.monotonic() - db_ok_at > 30:      # cek max 1× / 30s
        if not db.ping(timeout=0.2):
            return 503, "db unavailable"
        db_ok_at = time.monotonic()
    return 200, "ok"

# livez: JANGAN sentuh dependency
@app.get("/livez")
def livez():
    return 200 if event_loop_responsive() else 500

event_loop_responsive() untuk async runtime: jadwalkan callback, ukur delay. Delay > X = event loop blocked (deadlock sinkron di async code) → ini alasan sah untuk restart.

⚖️ Trade-off & Kapan JANGAN Dipakai

Ini bagian yang menentukan senior vs junior.

Round robin — jangan dipakai kalau:

• Durasi request heavy-tailed (search, export PDF, ML inference). RR mengabaikan antrean; p99 meledak karena satu host dapat 3 request lambat sekaligus.
• Host tidak homogen (beda instance type, beda cache state).
• Pool kecil (< 4) dengan request mahal — satu request lambat bisa memblok semua.

P2C — jangan dipakai kalau:

• N = 2. P2C dengan N=2 = "pilih yang lebih ringan dari keduanya" = perilaku yang sama dengan least-load penuh, tapi tanpa manfaat skala. Pakai least-request langsung atau RR.
• Load metric-nya noise (request sub-milidetik) → degenerasi ke random.
• Ada ketidakstabilan umpan balik: P2C bisa oscillate saat host yang dipilih jadi cepat sibuk lalu traffic lompat ke host lain. Mitigasi: kombinasi load + latency, atau hysteresis.

Consistent hashing — jangan dipakai kalau:

• Kamu tidak butuh affinity. Ini biaya (rebuild tabel, memory, hash computation) tanpa manfaat.
• Beban tidak merata secara natural (hot key). Consistent hashing tidak menyelesaikan hot key — itu masalah partisi key, bukan partisi host. Satu key viral tetap menghantam satu host.
• Endpoint sering berubah dan tabel besar (Maglev rebuild = O(slots × hosts)).

Active health check — jangan dipakai kalau:

• Dependency eksternal masuk ke probe → coupled failure domain (lihat di atas). Paling sering: DB, Redis, Kafka di /healthz.
• Traffic rendah (cron job, batch). Probe tiap 10s bisa jadi mayoritas traffic-mu dan mengacaukan metrik.
• Autoscaling berbasis CPU: probe gagal → pod dianggap unhealthy → HPA tidak scale down tapi restart loop mengacaukan sinyal.
• Kamu sudah punya passive check yang baik dan health check tidak representatif — kombinasi keduanya justru merusak (dokumentasi Envoy secara eksplisit menyebut uneject prematur).

Passive/outlier detection — hati-hati:

• max_ejection_percent default 10% berarti di cluster 5 host, kamu hanya boleh eject 0 host secara efektif (10% × 5 = 0.5 → dibulatkan, praktis tidak eject). Outlier detection praktis tidak berfungsi di cluster kecil tanpa always_eject_one_host atau penyesuaian. Ini penyebab "kenapa outlier detection tidak melakukan apa-apa" yang paling umum.
• Counter global → satu filter chain yang eject mempengaruhi filter chain lain di cluster yang sama (disebut eksplisit di docs Envoy).
• Ejection tanpa jitter → thundering herd saat rejoin (max_ejection_time_jitter default 0s; naikkan kalau cluster > ~50 host).

Health check interval — jangan terlalu agresif:

Probe 1s × 200 instance = 200 QPS overhead hanya untuk health check, dan itu masuk ke pool connection + worker thread. Untuk layanan yang butuh latensi ketat, probe itu sendiri jadi noise.

🏭 Contoh Produksi & Failure Mode

1. Readiness = liveness = "cek DB". DB failover 45 detik. Semua pod gagal /healthz → kubelet restart semuanya → 3 menit cold start → DB kena connection storm saat kembali → failover kedua. Outage 45 detik jadi 15 menit. Ini failure mode paling umum dan paling mahal.

2. Health check yang selalu 200. Proses hidup, event loop deadlock (blocking call di async handler). Probe 200. LB kirim traffic. Semua request timeout. Tidak ada yang restart karena liveness OK. Silent total outage dengan dashboard hijau. Deteksi: monitor actual request success rate, bukan probe.

3. Outlier detection di cluster 5 host. max_ejection_percent 10% → 0 host. Satu host rusak terus menerima 20% traffic. Error rate 20% stabil selama berjam-jam. Engineer bingung "kenapa outlier detection tidak jalan" — karena matematikanya.

4. Panic threshold menyembunyikan masalah. 60% host down → panic mode → traffic ke semua host termasuk yang down. Error rate 60% tapi load balancer melaporkan "semua host menerima traffic, tidak ada yang di-eject". Kalau kamu tidak tahu panic threshold ada, kamu akan mencari bug di tempat yang salah.

5. Slow start tidak ada di JVM. Deploy rolling 20 pod, masing-masing butuh 40 detik JIT warmup. Pod baru langsung dapat beban penuh → p99 3 detik → readiness tetap 200 (server merespons, cuma lambat) → tidak ada yang eject → semua user kena p99 selama 40 detik × 20 pod. Solusi: slow start window + readiness yang mengecek warmup (misal cache fill % atau JIT threshold), bukan cuma 200 OK.

6. Connection pool per-host tidak di-reset saat rejoin. Host di-eject 300s, kembali, tapi upstream connection pool masih penuh socket mati (half-open). Request pertama kena reset → 5xx → eject lagi. Loop 300s. Mitigasi: max_ejection_time lebih panjang dari TCP keepalive timeout, atau connection draining + GOAWAY di sisi server.

7. Sticky session vs rebalancing. Consistent hashing + host mati tanpa fallback policy → 1/N key hilang total (bukan cuma melambat). Dengan hash_policy fallback ke P2C, key tersebut tetap dilayani, hanya kehilangan cache affinity — degradasi, bukan outage.

⚠️ Miskonsepsi Umum

✅ Cek Pemahaman

1. Cluster 8 host, satu host punya bug yang menyebabkan 30% request-nya timeout (bukan error — timeout). Envoy dengan konfigurasi default (outlier detection aktif, max_ejection_percent 10%, consecutive_5xx 5). Apakah host itu akan di-eject? Jelaskan mekanismenya, dan sebutkan minimal dua perubahan konfigurasi untuk membuatnya benar-benar ter-eject tanpa membuat cluster rapuh.

2. Kamu punya layanan read-heavy dengan cache lokal per-instance dan 200 pod. Setiap pod butuh 90 detik untuk fill cache dari DB (kalau kosong, p99 = 4s). Deploy rolling update menghabiskan 20 menit. Jelaskan kenapa readiness probe saja tidak cukup, dan desain mekanisme apa yang mencegah p99 spike selama rollout. Sebutkan di mana mekanisme itu harus hidup (aplikasi, orchestrator, atau proxy) dan trade-off-nya.

3. Sebuah tim mengeluh: "Outlier detection kita eject host terus, tapi setelah 30 detik host itu balik dan langsung di-eject lagi, terus begitu selamanya. Kami sudah naikkan base_ejection_time jadi 5 menit, tetap saja." Sebutkan tiga hipotesis berbeda yang bisa menjelaskan gejala ini, dan untuk masing-masing, satu observability signal yang bisa membedakannya dari hipotesis lain.

🔑 Poin Kunci

• Load balancing = control loop. Kualitas keputusan terbatas oleh kualitas signal (load metric, error, latency), bukan oleh kecanggihan algoritma.
• P2C hampir sebaik "min dari semua" dengan biaya konstan — pilihan default yang masuk akal untuk pool besar. Degenerasi ke random kalau load metric noise.
• Active health check mendeteksi host mati; passive health check mendeteksi host rusak. Kamu butuh keduanya, dan keduanya bisa saling merusak kalau probe tidak representatif.
• /livez ≠ /readyz ≠ /startupz. Liveness yang mengecek dependency eksternal = restart storm. Ini bukan preferensi gaya; ini penyebab outage.
• Panic threshold (default 50%) sengaja membuang status kesehatan untuk menghindari cascade failure. Ketahui keberadaannya atau kamu akan mendiagnosis bug di tempat salah.
• max_ejection_percent (default 10%) membuat outlier detection praktis mati di cluster kecil. Hitung, jangan asumsikan.
• Slow start wajib untuk runtime dengan warmup (JVM, .NET, cache fill). Tanpa itu, rollout = p99 spike berkala.
• Consistent hashing menyelesaikan minimal disruption, bukan hot key. Dua masalah berbeda.
• Semua angka default di atas terverifikasi dari dokumentasi resmi Envoy (docs 1.41.0-dev) dan Kubernetes; angka itu bukan rekomendasi — hitung ulang dari SLA dan pola traffic-mu.

➡️ Eksplorasi Lanjut

• Backpressure & load shedding — apa yang terjadi setelah LB melakukan tugasnya benar tapi后端 tetap kewalahan. Terkait langsung: admission control, token bucket, retry budget (kenapa retry tanpa budget memperburuk outage).
• Retry + load balancing interaksi — retry ke host lain mengubah profil beban; retry budget per cluster (Envoy circuit_breakers + retry_budget) mencegah retry storm.
• Connection pooling & HTTP/2 multiplexing —为什么 max_concurrent_streams dan max_requests_per_connection mengubah efektivitas load balancing (host dengan satu koneksi H2 = satu "slot" untuk banyak request).
• Service mesh data plane vs client-side LB — kapan sidecar (Envoy) vs library (gRPC client-side LB) vs kernel (IPVS/eBPF). Trade-off: hop tambahan vs konsistensi kebijakan.
• Kubernetes EndpointSlice & topology-aware routing — trafficDistribution: PreferClose, zone-aware LB, dan failure mode saat zona terisolasi.
• Multi-cluster / global load balancing — latency-based routing, failover policy, dan kenapa global LB tanpa health check regional = traffic ke region mati.

Sumber terverifikasi: - Envoy Proxy docs, "Outlier detection" & "Panic threshold" (docs versi 1.41.0-dev, diakses 2026-10-31) — algoritma ejeksi, default max_ejection_percent 10%, base_ejection_time 30s, max_ejection_time 300s, interval 10s, panic threshold default 50%. - Envoy API reference config.cluster.v3.OutlierDetection — default consecutive_5xx 5, success_rate_stdev_factor 1900, failure_percentage_threshold 85, successful_active_health_check_uneject_host true, max_ejection_time_jitter 0s. - Kubernetes docs, "Configure Liveness, Readiness and Startup Probes" — semantik restart vs endpoint removal vs startup handoff. - Azar, Broder, Karlin, Upfal, "Balanced Allocations" (STOC 1994) — dasar analitis P2C. - Eisenbud et al., "Maglev: A Fast and Reliable Software Network Load Balancer" (NSDI 2016) — consistent hashing dengan lookup table. - Linkerd default: P2C + EWMA latency (dari desain default proxy; bukan benchmark, klaim arsitektur).

DIKETAHUI (dari docs resmi): semua angka default Envoy/K8s di atas. DIINFERENSI (dari prinsip, bukan diukur): contoh estimasi "outage 45 detik jadi 15 menit" adalah ilustrasi mekanisme, bukan data insiden spesifik. BELUM PASTI: perilaku persis implementasi Maglev di tiap proxy berbeda (ukuran tabel, rebuild strategy) — verifikasi di implementasi yang kamu pakai sebelum mengandalkan angkanya.