Robinhood, layanan load balancing internal buatan Dropbox

• Robinhood adalah layanan load balancing internal Dropbox yang diluncurkan pada 2020
• Layanan ini merutekan traffic internal antarserver untuk mendistribusikan beban layanan secara seimbang
• Sebelum Robinhood, sebagian besar layanan Dropbox mengalami kesulitan akibat distribusi beban yang tidak seimbang antar-backend
• Perbedaan hardware dan keterbatasan algoritme load balancing sebelumnya menyebabkan masalah keandalan akibat instance yang kelebihan beban
• Untuk mengatasinya, armada layanan harus di-provision secara berlebihan, yang berujung pada peningkatan biaya hardware

Fitur baru Robinhood

• Dengan memanfaatkan controller PID (Proportional-Integral-Derivative), Robinhood kini dapat menangani ketidakseimbangan beban dengan lebih cepat dan efektif
• Hal ini menghasilkan peningkatan keandalan infrastruktur dan penghematan biaya hardware yang signifikan
• Seiring meningkatnya workload AI yang menjalankan fitur-fitur cerdas terbaru, pengelolaan permintaan terhadap resource GPU secara efektif menjadi lebih penting dari sebelumnya

Tantangan load balancing di Dropbox

• Sistem service discovery Dropbox dapat diskalakan hingga ratusan ribu host di berbagai data center di seluruh dunia
• Beberapa layanan Dropbox memiliki jutaan klien, tetapi tidak mungkin membiarkan setiap klien terhubung ke semua instance server
  • Ini karena hal tersebut akan memberi tekanan memori yang terlalu besar pada server, dan saat server restart, TLS handshake dapat menyebabkan server kelebihan beban
• Sebagai gantinya, sistem service discovery menyediakan subset server yang dapat dihubungi oleh setiap klien
• Strategi load balancing terbaik yang tersedia bagi klien adalah melakukan round-robin atas daftar alamat yang diberikan oleh sistem service discovery
  • Namun, dengan metode ini beban tiap instance server bisa menjadi sangat tidak seimbang
  • Menambah ukuran subset adalah mitigasi yang mudah, tetapi tidak sepenuhnya menghilangkan ketidakseimbangan dan hanya menambah satu parameter lagi bagi pemilik layanan
• Masalah yang lebih mendasar adalah bahwa meskipun jumlah request yang dikirim ke tiap server sama, hardware dasar tiap server bisa berbeda
  • Artinya, request yang sama mengonsumsi jumlah resource yang berbeda pada kelas hardware yang berbeda
• Intinya, klien tidak memiliki visibilitas terhadap beban server
• Di masa lalu, Dropbox mencoba mengatasi masalah ini dengan membuat server melampirkan informasi beban pada response header
  • Klien kemudian dapat melakukan load balancing sendiri dengan memilih endpoint dengan beban terendah dari subset alamat tersebut
  • Hasilnya menjanjikan, tetapi tetap ada beberapa kekurangan
    • Karena dibutuhkan perubahan kode baik di sisi server maupun klien untuk header beban khusus ini, pendekatan tersebut sulit diadopsi secara global
    • Hasilnya bagus, tetapi belum cukup bagus

Keputusan membangun Robinhood

• Pada 2019, Dropbox secara resmi memutuskan untuk membangun Robinhood
• Layanan baru ini dibangun di atas sistem service discovery internal yang sudah ada, mengumpulkan informasi beban dari server lalu melampirkannya ke informasi routing
• Robinhood memanfaatkan Endpoint Discovery Service milik Envoy untuk mengintegrasikan informasi beban ke dalam bobot endpoint, sehingga klien dapat melakukan weighted round-robin
• Karena komunitas gRPC sedang mengadopsi protokol Envoy xDS, Robinhood kompatibel baik dengan klien Envoy maupun gRPC
• Saat itu tidak ada solusi load balancing yang sudah ada yang memenuhi kebutuhan Dropbox, sehingga mereka memutuskan membangun layanan baru

Hasil Robinhood

• Setelah digunakan selama beberapa tahun di lingkungan produksi, Robinhood menunjukkan hasil yang menjanjikan
• Layanan ini berhasil mengurangi ukuran fleet beberapa layanan besar hingga 25%, sehingga menghemat biaya hardware yang signifikan setiap tahun
• Keandalan juga meningkat karena proses yang terlalu banyak dimanfaatkan berkurang

Arsitektur Robinhood

• Instance Robinhood diterapkan di setiap data center dan terdiri dari tiga bagian: layanan load balancing, proxy, dan database routing

Layanan load balancing (LBS)

• Inti dari Robinhood
• Bertugas mengumpulkan informasi beban dan menghasilkan informasi routing yang mencakup bobot endpoint
• Karena beberapa instance memperbarui informasi routing untuk layanan secara bersamaan, Robinhood menggunakan shard manager internal untuk menetapkan worker utama bagi tiap layanan
• Karena tiap layanan bersifat independen, LBS dapat dipartisi per layanan dan diskalakan secara horizontal

Proxy

• Bertugas merutekan informasi beban layanan ke partisi LBS yang sesuai di dalam data center
• Penggunaan proxy juga mengurangi jumlah koneksi langsung ke proses LBS
  • Tanpa proxy, semua proses LBS harus terhubung ke semua node di dalam infrastruktur
  • Sebaliknya, proses LBS hanya perlu terhubung ke proxy, sehingga tekanan memori pada LBS berkurang secara signifikan
• Proxy hanya terhubung ke node dalam data center yang sama, sehingga dapat diskalakan secara horizontal
• Pola ini digunakan di banyak bagian infrastruktur untuk melindungi layanan agar tidak menerima terlalu banyak koneksi TLS

Database routing

• Database berbasis ZooKeeper/etcd yang menyimpan informasi routing layanan, seperti nama host, alamat IP, dan bobot yang dihasilkan LBS
• ZooKeeper dan etcd dapat memberi tahu semua watcher secara real-time tentang perubahan node/key, dan sangat cocok untuk use case service discovery Dropbox yang berfokus pada pembacaan
• Konsistensi eventual yang dijamin oleh ZooKeeper/etcd juga sudah memadai untuk service discovery

Melihat lebih dekat layanan load balancing

• Tujuan load balancing adalah membuat tingkat utilisasi semua node sama dengan utilisasi rata-rata
• Dengan menggunakan controller PID, Robinhood menjaga utilisasi tiap node hampir sama dengan utilisasi rata-rata
• LBS membuat controller PID untuk setiap node dan menggunakan utilisasi rata-rata sebagai setpoint
• LBS menggunakan output controller PID sebagai delta untuk bobot endpoint, lalu menormalkan bobot di antara semua endpoint layanan
• Node baru memang memerlukan beberapa kali penyesuaian untuk konvergen ke utilisasi rata-rata, tetapi controller PID sangat efektif untuk load balancing

Skenario operasi LBS

• LBS dirancang untuk menangani berbagai skenario yang dapat memengaruhi load balancing, mulai dari restart node hingga laporan beban yang hilang
• Untuk mempertahankan performa optimal, LBS menerapkan beberapa strategi untuk menangani kasus-kasus pengecualian ini

Startup LBS

• LBS menyimpan informasi beban dan status controller PID di memori
• Saat LBS restart, ia tidak langsung mulai memperbarui bobot, melainkan menunggu sebentar hingga laporan beban masuk
• Untuk bobot controller PID, LBS memulihkannya dengan membaca bobot endpoint dari database routing

Node cold start

• Karena node baru sering bergabung ke fleet layanan, penting untuk mencegah masalah Thundering Herd
• Karena utilisasi awal node baru biasanya 0, LBS menetapkan bobot node baru ke bobot endpoint yang rendah, lalu membiarkan controller PID menaikkan node tersebut hingga mencapai utilisasi rata-rata

Laporan beban yang hilang

• Dalam lingkungan sistem terdistribusi, kegagalan adalah hal yang umum
• Karena kemacetan jaringan atau kegagalan hardware, laporan beban dari beberapa node bisa terlambat atau tidak sampai
• LBS melewati node-node tersebut saat memperbarui bobot, sehingga bobot endpointnya tidak berubah
• Namun, jika banyak laporan beban yang hilang, perhitungan utilisasi rata-rata bisa menjadi tidak akurat
• Demi keamanan, dalam kasus ini LBS akan sepenuhnya melewati tahap pembaruan bobot

Metrik utilisasi

• Utilisasi CPU adalah metrik load balancing yang paling banyak digunakan di Dropbox
• Untuk layanan yang tidak mengalami bottleneck pada CPU, jumlah request yang sedang berjalan merupakan ukuran alternatif yang baik
• LBS diimplementasikan untuk mendukung load balancing berdasarkan CPU dan/atau request yang sedang berjalan

Keterbatasan

• Controller PID membentuk loop umpan balik untuk menjaga utilisasi node tetap dekat dengan nilai targetnya, yaitu utilisasi rata-rata
• Jika umpan balik sangat sedikit, seperti pada layanan dengan traffic sangat rendah atau request berlatensi sangat tinggi yang diukur dalam hitungan menit, load balancing tidak akan efektif
• Layanan dengan request berlatensi tinggi sebaiknya bersifat asynchronous

Routing antar-data center

• Instance LBS menangani load balancing di dalam data center
• Routing antar-data center memiliki pertimbangan yang berbeda
  • Misalnya, Dropbox ingin merutekan request ke data center terdekat untuk mengurangi round-trip time request
• Untuk itu, Dropbox memperkenalkan konfigurasi locality yang mendefinisikan pembagian traffic antar-data center

Evaluasi performa load balancer

• Performa load balancing diukur dengan rasio max/avg
  • Jika pemilik layanan memilih load balancing berdasarkan CPU, maka maxCPU/avgCPU digunakan sebagai metrik performa
  • Pemilik layanan umumnya melakukan provisioning layanan berdasarkan utilisasi maksimum antar node, karena tujuan utama load balancing adalah mengurangi ukuran fleet
• Strategi load balancing dengan kontroler PID dapat menjaga rasio max/avg tetap mendekati 1

Grafik evaluasi performa load balancing

• Grafik yang menunjukkan max/avg CPU dan p95/avg CPU dari klaster proxy Envoy terbesar
  • Setelah load balancing berbasis kontroler PID diaktifkan, kedua metrik turun mendekati 1
  • Rasio max/avg turun dari 1,26 menjadi 1,01, menunjukkan peningkatan 20%
• Grafik yang menunjukkan analisis persentil utilisasi CPU per node
  • Setelah load balancing berbasis kontroler PID diaktifkan, max, p95, avg, dan p5 hampir menyatu menjadi satu garis
• Grafik lain yang menunjukkan max/avg CPU dan p95/avg CPU dari klaster frontend database terbesar
  • Setelah load balancing berbasis kontroler PID diaktifkan, kedua metrik turun mendekati 1
  • Rasio max/avg turun dari 1,4 menjadi 1,05, menunjukkan peningkatan 25%
• Grafik lain yang menunjukkan analisis persentil utilisasi CPU per node
  • Setelah load balancing berbasis kontroler PID diaktifkan, max, p95, avg, dan p5 sekali lagi hampir menyatu menjadi satu garis

Alasan membangun Config Aggregator

• Robinhood menyediakan beberapa opsi yang dapat dipilih pemilik layanan dan juga dapat menerapkan perubahan secara dinamis
• Pemilik layanan membuat dan memperbarui konfigurasi Robinhood untuk layanannya di direktori layanan dalam codebase
• Pengaturan ini disimpan dalam layanan manajemen konfigurasi, yaitu library praktis yang menerima perubahan konfigurasi Robinhood secara real-time
• Namun, karena beberapa masalah, tidak memungkinkan untuk secara rutin membangun dan mendorong mega-konfigurasi Robinhood dari codebase
  • Jika perubahan diperkenalkan lewat push konfigurasi, menekan tombol rollback berisiko
    • Karena tidak diketahui berapa banyak layanan lain yang berubah sejak push terakhir
  • Tim yang memiliki Robinhood juga bertanggung jawab atas setiap push mega-konfigurasi
    • Ini berarti tim Robinhood harus terlibat dalam setiap push konfigurasi yang berubah, yang merupakan pemborosan waktu engineering
    • Karena sebagian besar insiden dapat diselesaikan oleh pemilik layanan
  • Untuk meminimalkan potensi risiko, setiap push membutuhkan waktu berjam-jam untuk diterapkan ke beberapa data center
• Untuk mengatasi masalah ini, mereka membangun layanan kecil lain bernama Config Aggregator

Config Aggregator

• Config Aggregator mengumpulkan semua konfigurasi per layanan dan menyusun mega-konfigurasi yang akan digunakan oleh LBS
• Config Aggregator memantau konfigurasi per layanan dan menyebarkan perubahan ke mega-konfigurasi secara real-time
• Config Aggregator juga menyediakan fitur tombstone untuk mencegah konfigurasi Robinhood suatu layanan terhapus secara tidak sengaja
  • Jika pemilik layanan mendorong perubahan yang menghapus layanan dari konfigurasi Robinhood, Config Aggregator tidak langsung menghapus entri layanan, melainkan menandainya sebagai tombstone
  • Penghapusan sebenarnya terjadi beberapa hari kemudian
  • Fitur ini juga menyelesaikan race condition yang dapat terjadi karena siklus push yang berbeda antara konfigurasi Robinhood dan konfigurasi routing lain (misalnya, konfigurasi Envoy)
• Kekurangan layanan manajemen konfigurasi adalah saat ini belum memiliki versioning
• Mega-konfigurasi dicadangkan secara berkala untuk berjaga-jaga jika konfigurasi LBS perlu dikembalikan ke kondisi baik yang telah diketahui

Strategi migrasi

• Mengganti strategi load balancing sekaligus bisa berisiko
• Karena itulah Robinhood memungkinkan beberapa strategi load balancing dikonfigurasi untuk suatu layanan
• Dropbox memiliki feature gate berbasis persentase, sehingga diterapkan strategi campuran di mana klien menggunakan jumlah berbobot dari bobot yang dihasilkan oleh dua strategi load balancing sebagai bobot endpoint
• Dengan cara ini, semua klien dapat bermigrasi secara bertahap ke strategi load balancing baru sambil tetap melihat alokasi bobot yang sama untuk endpoint

Pelajaran yang dipetik

• Selama merancang dan mengimplementasikan Robinhood, mereka memperoleh beberapa pelajaran utama tentang apa yang efektif dan apa yang tidak
• Dengan memprioritaskan kesederhanaan, meminimalkan perubahan klien, dan merencanakan migrasi sejak awal, mereka dapat menyederhanakan pengembangan dan deployment LBS serta menghindari jebakan mahal

Konfigurasi harus sesederhana mungkin

• Robinhood memperkenalkan banyak opsi yang bisa dikonfigurasi oleh pemilik layanan
• Namun, dalam kebanyakan kasus, yang mereka butuhkan hanyalah pengaturan default yang disediakan
• Konfigurasi default yang baik dan sederhana (atau lebih baik lagi tanpa konfigurasi) dapat menghemat sangat banyak waktu engineering

Perubahan pada klien juga harus tetap sederhana

• Peluncuran perubahan ke klien internal bisa memakan waktu berbulan-bulan
  • Sebagian besar deployment didorong setiap minggu, tetapi banyak juga yang hanya sebulan sekali atau bahkan tidak pernah di-deploy selama bertahun-tahun
• Semakin banyak perubahan yang bisa dipindahkan ke LBS, semakin baik
  • Misalnya, sejak awal mereka memutuskan menggunakan weighted round robin dalam desain klien dan tidak mengubahnya sejak saat itu
  • Ini sangat mempercepat laju progres
• Membatasi sebagian besar perubahan ke LBS juga mengurangi risiko stabilitas
  • Karena perubahan pada LBS dapat di-rollback dalam hitungan menit bila diperlukan

Migrasi harus direncanakan pada tahap perancangan proyek

• Migrasi menghabiskan waktu engineering dalam jumlah besar
• Ada juga risiko stabilitas yang perlu dipertimbangkan
• Ini bukan pekerjaan yang menyenangkan, tetapi penting
• Saat merancang layanan baru, perlu dipikirkan sedini mungkin bagaimana use case lama dapat dimigrasikan dengan mulus ke layanan baru
• Semakin banyak hal yang diminta dari pemilik layanan, semakin besar kemungkinan migrasi menjadi mimpi buruk
  • Terutama untuk komponen infrastruktur dasar
• Proses migrasi Robinhood tidak dirancang dengan baik sejak awal, sehingga mereka menghabiskan jauh lebih banyak waktu daripada perkiraan untuk mengimplementasikan ulang proses dan mendesain ulang konfigurasi
• Waktu engineering yang dibutuhkan untuk migrasi harus menjadi indikator utama keberhasilan

Dampak Robinhood

• Setelah sekitar satu tahun di lingkungan produksi, dapat dikatakan bahwa iterasi terbaru Robinhood secara efektif menyelesaikan tantangan load balancing Dropbox yang telah lama ada
• Algoritme inti berupa kontroler PID menunjukkan hasil yang menjanjikan dan menghadirkan peningkatan performa yang signifikan pada layanan terbesar
• Mereka juga memperoleh wawasan berharga tentang perancangan dan pengoperasian layanan load balancing pada skala Dropbox

Catatan kaki

1. Misalkan N, M, dan s masing-masing adalah jumlah server, jumlah klien, dan ukuran subset alamat. Jumlah klien yang terhubung ke server mengikuti sampel dari distribusi binomial B(M, s/n). Seperti disebutkan sebelumnya, klien melakukan round robin sederhana terhadap himpunan alamat yang diberikan oleh service discovery. Karena itu, jika setiap klien mengirimkan jumlah request yang kira-kira sama, distribusi beban di sisi server akan menyerupai distribusi binomial.

2. Sistem service discovery yang ada diperluas untuk mendukung protokol gRPC xDS (A27). Pada saat blog ini ditulis, klien gRPC belum mendukung weighted round robin untuk bobot endpoint dari control plane, sehingga mereka mengimplementasikan picker weighted round robin kustom berdasarkan shortest deadline first scheduling.

3. Ada kasus menarik di mana suatu layanan sesekali mengalami kemacetan karena I/O dengan performa yang menurun. Dalam situasi seperti ini, CPU pada node tersebut tetap rendah, dan LBS mulai menaikkan bobot node untuk menaikkan CPU ke rata-rata, yang berujung pada dead spiral. Sebagai solusi, mereka menggunakan nilai maksimum dari CPU dan request yang sedang berlangsung sebagai metrik beban untuk menyeimbangkan layanan.

Opini GN⁺

• Robinhood tampak sebagai layanan yang sangat baik untuk menyelesaikan tantangan load balancing di Dropbox secara efektif. Penggunaan kontroler PID sangat mengesankan
• Ini adalah contoh yang menunjukkan dengan jelas betapa sulitnya load balancing pada infrastruktur global berskala sangat besar. Ada banyak hal yang harus dipertimbangkan, seperti perbedaan hardware, distribusi beban yang tidak merata, dan kemacetan jaringan
• Merancang agar semua komponen dapat terhubung dan bekerja secara organik tampak sangat penting. LBS, proxy, dan routing DB dipisahkan, tetapi saling berinteraksi erat secara real-time
• Grafik yang mengukur secara kuantitatif performa load balancing dan memvisualisasikan area perbaikan sangat mengesankan. Khususnya, ini menunjukkan dengan baik bahwa menjaga rasio max/avg tetap mendekati 1 penting untuk optimasi ukuran armada
• Penerapan Config Aggregator untuk memisahkan konfigurasi per layanan juga tampak sebagai ide yang baik. Ini memungkinkan pemilik layanan mengelola perubahan mereka secara independen
• Penyediaan pengaman seperti tombstone juga merupakan detail yang cermat. Mencegah penghapusan konfigurasi akibat kesalahan adalah hal yang penting
• Pelajaran tentang strategi migrasi juga tampak berguna. Jika migrasi tidak dipertimbangkan sejak awal, banyak waktu bisa terbuang di kemudian hari
• Secara keseluruhan, Robinhood tampak sebagai solusi yang sistematis dan matang untuk load balancing pada skala Dropbox. Ini merupakan contoh yang layak dijadikan referensi oleh perusahaan lain dengan infrastruktur berskala besar

Solusi serupa:

• Elastic Load Balancing (ELB) milik AWS dan Cloud Load Balancing milik Google Cloud juga menyediakan layanan terkelola untuk load balancing skala besar
• Dalam kasus Kubernetes, memang ada load balancer bawaannya sendiri (kube-proxy), tetapi jika memanfaatkan solusi service mesh seperti Istio atau Linkerd, fitur load balancing dan manajemen traffic yang lebih kuat dapat digunakan
• Zuul milik Netflix dan Envoy milik Lyft juga menyediakan fungsi load balancing berbasis proxy

Hal yang perlu dipertimbangkan saat adopsi:

• Perlu memastikan kompatibilitas dengan infrastruktur dan layanan yang sudah ada. Jika migrasi diperlukan, strateginya harus disusun
• Dampaknya terhadap performa dan stabilitas harus diuji dan dimonitor secara memadai. Bug dalam logika load balancing bisa berakibat fatal
• Cakupan dan kecepatan adopsi perlu ditentukan dengan mempertimbangkan kemampuan tim. Daripada menerapkannya ke seluruh sistem secara tergesa-gesa, pendekatan bertahap akan lebih baik
• Dalam jangka panjang, dibutuhkan upaya berkelanjutan untuk terus mengoptimalkan dan meningkatkan sistem. Aktivitas seperti menyesuaikan algoritme load balancing dengan situasi dan menghilangkan titik bottleneck akan sangat membantu

[kbumsik]

Menarik juga mendengar soal pengontrol PID di dunia software, hehe.