Power of Two Choices Mengurangi Ketimpangan Load dengan Dua Sampel

Load balancer yang memilih satu destination secara acak memiliki biaya kecil dan mudah didesentralisasi, tetapi penempatan acak dapat menghasilkan queue yang tidak merata. Pada sisi lain, memilih destination dengan load terendah dari seluruh pool membutuhkan informasi load terbaru untuk setiap kandidat dan dapat membuat load balancer sendiri menjadi mahal.

Strategi power of two choices berada di antara kedua desain tersebut. Untuk setiap request, ambil dua destination yang memenuhi syarat, bandingkan sinyal load, lalu kirim request ke kandidat yang lebih baik. Dua observasi cukup untuk menghindari banyak penempatan buruk tanpa memerlukan pencarian global.

Algoritmanya kecil, tetapi perilaku produksi bergantung pada kandidat yang diambil, sinyal load yang dibandingkan, dan tingkat staleness sinyal tersebut.

Seleksi tetap lokal pada dua kandidat

Untuk pool backend yang memenuhi syarat, keputusan dasarnya:

a = random_backend()
b = random_backend(excluding=a)

if load(a) <= load(b):
    choose a
else:
    choose b

Request tetap memakai randomization sehingga load balancer independen tidak membutuhkan satu urutan global untuk seluruh backend. Sampel kedua memberi setiap request peluang menghindari destination yang sudah lebih sibuk daripada peer acak lainnya.

Mengambil lebih banyak kandidat dapat memperbaiki placement lebih jauh, tetapi setiap sampel tambahan menambah biaya observasi dan keputusan. Dua kandidat menarik karena memberi peningkatan balancing yang besar sambil menjaga selection path tetap kecil.

Metrik load menentukan keputusan

“Load lebih rendah” bukan satu pengukuran universal. Active request, queue length, outstanding byte, CPU utilization, estimated completion time, atau kombinasi berbobot dapat sesuai untuk sistem yang berbeda.

Jumlah active request bekerja baik ketika biaya antar-request relatif serupa. Metrik ini dapat menyesatkan jika satu backend memiliki dua request mahal sementara backend lain memiliki sepuluh request ringan. Queue length memiliki keterbatasan serupa ketika ukuran job sangat bervariasi.

Metrik sebaiknya mengikuti resource yang paling langsung membatasi service. Connection proxy mungkin berfokus pada active connection, sedangkan worker pool dapat berfokus pada queued work. Perbandingan tidak memerlukan kebenaran global yang sempurna, tetapi sinyal harus cukup berguna untuk membedakan kandidat yang jelas lebih buruk dari kandidat yang lebih baik.

Observasi stale mengurangi presisi tanpa memerlukan consensus global

Load berubah terus-menerus. Load balancer yang menunggu metrik tersinkronisasi sempurna akan menambah biaya koordinasi pada jalur yang semestinya murah.

Banyak implementasi memakai counter lokal atau laporan load terbaru. Staleness dapat menghasilkan pilihan yang sesekali kurang optimal, tetapi algoritma tidak membutuhkan consensus snapshot untuk seluruh fleet.

Risiko meningkat ketika update sangat terlambat atau request berukuran besar dibanding kapasitas backend. Beberapa load balancer dapat sama-sama melihat backend yang sama sebagai ringan lalu mengirim burst ke sana sebelum update metrik berikutnya. Random sampling membantu menyebarkan keputusan, tetapi tidak menghapus reaksi serempak terhadap data stale.

Accounting per load balancer dapat mengurangi celah ini dengan langsung memasukkan request yang baru saja ditempatkan oleh balancer tersebut, bahkan sebelum telemetry remote menyusul.

Eligibility ditentukan sebelum membandingkan load

Dua kandidat harus sudah memenuhi routing constraint. Backend di tenant boundary lain, protocol version yang tidak kompatibel, kondisi unhealthy, atau zone yang tidak diizinkan bukan pilihan valid hanya karena queue-nya lebih pendek.

Selection path yang praktis lebih dulu mengambil kandidat dari eligible set berdasarkan health, locality, capacity class, shard ownership, dan policy. Perbandingan load kemudian memilih antara kandidat yang secara semantik dapat saling menggantikan untuk request tersebut.

Weight juga penting ketika kapasitas backend berbeda. Membandingkan active-request count mentah antara worker 4-core dan 32-core dapat memilih mesin kecil pada waktu yang keliru. Normalized load atau weighted sampling dapat merepresentasikan kapasitas heterogen dengan lebih tepat.

Request lambat dapat mendistorsi balancing berbasis active count

Strategi least-active menganggap concurrency saat ini sebagai proxy yang berguna untuk completion di masa dekat. Request berumur panjang menguji asumsi tersebut.

Backend dengan beberapa operasi lambat akan tetap ditandai sibuk, dan itu berguna. Namun, jika biaya request baru terlihat setelah eksekusi dimulai, satu request mahal yang baru ditempatkan dapat mengubah load efektif backend jauh lebih besar daripada yang ditunjukkan counter.

Sistem dengan variasi ukuran job yang tinggi dapat memasukkan estimasi biaya, memisahkan queue berdasarkan workload class, atau memakai bounded concurrency per class. Power of two choices memperbaiki placement rule; teknik ini tidak mengisi informasi biaya request yang memang tidak tersedia.

Retry perlu mengambil sampel baru

Retry yang kembali ke destination overload yang sama dapat mempertahankan penempatan buruk sebelumnya. Jika operasi mengizinkan retry, attempt baru umumnya perlu menjalankan kembali keputusan eligibility dan load kecuali affinity atau consistency constraint mengharuskan hal lain.

Retry juga menambah load. Load balancer tidak boleh memperlakukan retry traffic sebagai kerja gratis hanya karena selection lebih merata. Retry budget, deadline, dan admission control tetap diperlukan ketika failure atau overload meningkatkan jumlah attempt.

Hal yang sama berlaku untuk hedged request. Setiap attempt tambahan perlu langsung dihitung dalam load backend agar speculative traffic ikut memengaruhi keputusan balancing.

Observability perlu menampilkan kualitas kandidat

Utilization backend agregat dapat terlihat sehat sementara selection policy berulang kali membuat hotspot lokal. Telemetry lebih berguna ketika merekam load kedua kandidat dan destination yang dipilih.

Sinyal yang berguna mencakup:

• load kandidat A dan kandidat B saat selection;
• load kandidat terpilih dan kandidat yang ditolak;
• active work dan queue depth per backend;
• frekuensi tie;
• saturation backend setelah assignment;
• distribusi request antar-capacity class;
• retry dan hedge attempt yang ikut dihitung sebagai load.

Pengukuran ini dapat menunjukkan metrik yang stale, normalisasinya buruk, atau korelasinya lemah terhadap service time aktual.

Dua pilihan mempertahankan desentralisasi

Daya tarik operasional utama strategi ini bukan kemampuannya selalu menemukan backend dengan load terendah secara global. Strategi ini memang tidak menuntut hal tersebut.

Setiap request membuat perbandingan acak yang kecil. Dalam jumlah request yang besar, keputusan lokal tersebut mengurangi konsentrasi sambil membiarkan banyak load balancer beroperasi tanpa memelihara urutan total yang presisi untuk seluruh fleet.

Boundary ini penting. Power of two choices adalah primitive placement, bukan admission control, health checking, atau capacity planning. Teknik ini paling efektif ketika candidate set sudah valid, sinyal load mencerminkan tekanan yang berarti, dan setiap assignment segera memperbarui pengetahuan lokal.

Dengan kondisi tersebut, satu sampel tambahan dapat menghilangkan banyak ketimpangan dari random routing satu pilihan tanpa mengubah setiap request menjadi scheduling query ke seluruh fleet.