Cloudflare membawa algoritma konsensus yang jarang dipakai ke sistem internal: QuePaxa. Algoritma ini dipublikasikan pada 2023 oleh peneliti Tennage & Băsescu dan lainnya, dan dijadikan dasar bagi Meerkat, layanan yang mengelola kontrol global jaringan perusahaan.

Perusahaan menjelaskan QuePaxa sebagai pilihan yang tidak biasa. Mayoritas sistem konsensus mengandalkan algoritma baku seperti Raft, Multi-Paxos, atau Viewstamped Replication. Algoritma-algoritma tersebut sudah matang, dipahami dengan baik, dan biasanya bekerja dengan baik. Namun, Cloudflare mencatat bahwa mereka sering melemah saat jaringan lebar memiliki keterlambatan variabel, seperti internet, di mana konsensus harus mengejar akurasi meskipun terjadi peningkatan latensi dan koneksi putus-putus.

QuePaxa menyelesaikan masalah itu dengan tidak mengandalkan pemimpin tunggal yang stabil. Mekanisme ini mengizinkan beberapa peserta mengajukan usulan sekaligus, menggunakan prioritas acak untuk mencapai konsensus. Cloudflare mengatakan pendekatan ini jauh lebih baik dalam kondisi kondisi luas yang tidak menentu.

Meerkat adalah sistem terdistribusi di mana serangkaian replika setuju terhadap urutan kejadian yang diurutkan. Setiap kejadian diputuskan oleh algoritma konsensus. Tujuan utamanya adalah menjamin bahwa replika tidak pernah memutuskan nilai yang bertentangan. Sistem ini memperlihatkan perilaku seperti penyimpanan kunci-nilai di mana setiap entri log adalah operasi baca atau tulis.

Perbedaan utama dari sistem serupa adalah skalanya. Sebuah klaster Meerkat dapat tersebar di berbagai benua dengan tautan yang sering menunjukkan latensi tinggi dan fluktuatif. Sistem konsensus umumnya dijalankan di jaringan yang lebih kecil dan memiliki kebutuhan latensi yang ketat. Di internet, kegagalan sering berasal dari jaringan, bukan dari server.

Cloudflare mengamati bahwa banyak algoritma konsensus menjadi tidak tersedia atau lambat secara tidak proporsional saat kondisi jaringan memburuk meskipun tidak ada replika yang gagal. Pada tahun 2020, sebagian gagalnya switch inti jaringan menyebabkan sistem berbasis konsensus mengalami penurunan kinerja yang luar biasa: dashboard beroperasi sekitar 80 kali lebih lambat dari biasanya.

Algoritma konsensus umumnya mengandalkan deteksi kegagalan yang dapat memberi tahu replika kapan pemimpin telah mati. Namun, dalam jaringan asinkron, sulit membedakan antara server yang macet dan jaringan yang mengalami keterlambatan. Detektor harus membuat perkiraan berdasarkan cara kegagalan terdeteksi. Jika perkiraan tersebut keliru, seluruh sistem harus berhenti hingga pemimpin baru terpilih.

Cloudflare mencatat bahwa deteksi kegagalan sebagian besar bersifat perkiraan. Proses tidak dapat mengamati langsung bahwa proses jarak jauh telah gagal. Ia hanya dapat mengamati bahwa pesan yang diharapkan telah sampai atau belum. Pola komunikasi yang dapat diprediksi, seperti heartbeats, menentukan kesehatan mesin. Ketika pesan datang terlambat atau tidak sama sekali, detektor harus mengambil keputusan dengan informasi yang tidak sempurna.

Dalam jaringan lebar, ketinggian latensi membuat deteksi makin lambat. Raft misalnya memperlukan timeout pemilihan sekitar lima hingga sepuluh kali putaran perjalanan pulas jaringan. Timeout minimalnya terkunci oleh latensi jaringan itu sendiri. Akibatnya, penemuan pemimpin yang gagal dapat memakan waktu sekitar satu detik, dan sistem tidak dapat memproses sampai deteksi tersebut tuntas.

QuePaxa menghilangkan kebutuhan akan pemilihan pemimpin yang bergantung pada deteksi kegagalan. Cloudflare menjelaskan bahwa algoritma ini dirancang untuk lingkungan asinkron, di mana protokol tidak mengandalkan jaringan yang baik atau ketepatan waktu yang eksak. Algoritma ini menemukan kesepakatan dengan tiga pilihan desain utama: pemimpin opsional, penghapusan ketergantungan pada pembawa pesan, dan mekanisme acak.

Dalam QuePaxa, ada dua peran: pembawa usulan dan perekam. Pembawa usulan mengirimkan usulan, sementara perekam bertindak sebagai perantara yang mencatat setiap usulan yang mereka terima. Alih-alih berkompetisi untuk mencapai keputusan, pembawa usulan bekerjasama menyesuaikan usulan yang mendukung satu kesepakatan.

Setiap usulan mendapat prioritas dalam bentuk angka acak. Pemimpin opsional memiliki prioritas maksimum eksklusif. Selama eksekusi, pembawa usulan mengajukan usulan mereka ke perekam, yang menyebarkan usulan tersebut. Sistem ini mengizinkan setiap klien mengajukan usulan tanpa dipaksa ke pemimpin tertentu.

Cloudflare menjelaskan bahwa prioritas acak dan adopsi usulan mencegah pembawa usulan berkompetisi. Semakin banyak pembawa usulan yang mengajukan usulan, semakin besar peluang mereka untuk menemukan usulan dengan prioritas tertinggi. Inilah yang membuat QuePaxa menjadi algoritma acak: prioritas acak dari pembawa usulan non-pemimpin menciptakan jalur konvergensi.

Satu pembawa usulan ditunjuk sebagai pemimpin. Pemimpin adalah satu-satunya pembawa usulan yang dapat memutuskan dalam satu perjalanan pulas. Pemimpin selalu mengajukan usulan dengan prioritas tertinggi. Jika pemimpin mengetahui bahwa usulannya menyebar sebelum pembawa usulan lainnya, ia dapat memutuskan segera. Klien tidak terpaksa melakukan permintaan ke pemimpin; setiap pembawa usulan dapat mengajukan usulan.

Karena hanya satu yang dapat memutuskan dalam satu perjalanan pulas, Cloudflare membuat keputusan tersebut dapat dimanfaatkan sesuai keinginan. Klien yang mengirim usulan melakukan penyangga: mereka mengirim permintaan ke setiap replika, dan replika non-pemimpin menunggu batas waktu kecil. Jika pemimpin berhasil mengirim sebelum waktu habis, keputusan dapat diambil tanpa menunggu deteksi kegagalan.

Batas waktu penyangga ini berbeda dengan timeout dalam Raft atau Multi-Paxos. Ia bukan deteksi kegagalan dan tidak dibatasi oleh latensi jaringan. Ia ditentukan secara lokal oleh replika dan dapat sekecil yang diinginkan. Dalam Raft, batas waktu lima milidetik dalam jaringan dengan latensi seratus milidetik akan membuat sistem menjadi macet. Dalam QuePaxa, batas waktu penyangga lima milidetik berfungsi tanpa membekukan sistem.

Jika pemimpin QuePaxa mati, sistem dapat pulih dengan cepat tanpa dibatasi oleh latensi jaringan. Karena setiap orang dapat mengajukan usulan, bukan hanya pemimpin, QuePaxa dapat menangani kegagalan pemimpin secara proaktif melalui penyangga, bukan merespons kegagalan. Cloudflare mencatat bahwa perekam memiliki sifat interseksi mayoritas, yang memastikan bahwa dua set mayoritas dari perekam selalu berbagi setidaknya satu perekam.

Algoritma QuePaxa beroperasi dalam beberapa fase per round. Jika usulan belum ditentukan dalam fase terakhir, round berikutnya dimulai dari awal. Setiap majelis, pembawa usulan menyebarkan usulan yang telah diadopsi ke semua perekam. Setelah menerima balasan dari mayoritas perekam, mereka maju ke fase berikutnya.

Fase 0 adalah jalur cepat pemimpin: acak prioritas, periksa apakah pemimpin telah mencapai mayoritas, dan bantu pembawa usulan bersatu jika pemimpin gagal. Prioritas penawaran pemimpin tidak diacak dan selalu memiliki prioritas maksimum yang tersedia.

Jika ada pembawa usulan konkuren, jalur cepat tidak dijamin. Pemimpin mungkin gagal mencapai mayoritas terlebih dahulu atau menerima satu balasan yang mendukung pembawa usulan lain. Dalam hal ini, pembawa usulan beradaptasi dengan usulan prioritas tertinggi yang mereka terima dari mayoritas dan maju ke fase kedua.

Fase 1 menyebarkan usulan yang diadopsi ke mayoritas perekam. Perekam melacak usulan prioritas tertinggi yang mereka amati. Langkah ini mencegah protokol memutuskan usulan dengan prioritas lebih rendah nanti. Hal ini juga harus berkat interseksi mayoritas.

Fase 2 adalah keputusan. Setiap pembawa usulan menentukan apakah usulan dengan prioritas lebih tinggi mengalahkan usulannya dengan menanyakan mayoritas perekam tentang usulan prioritas tertinggi yang mereka amati pada fase 1. Jika usulan yang dikembalikan masih usulannya, mereka memutuskan. Dalam contoh Cloudflare, pemimpin melihat usulannya dikembalikan oleh mayoritas dan memutuskan dengan aman.

Fase 3 adalah pembersihan akhir untuk mempersiapkan round berikutnya. Pembawa usulan menyebarkan usulan mereka lagi dan mengadopsi hasil terbaik dari mayoritas perekam. Dalam contoh tersebut, pembawa usulan yang tersisa menemukan usulan yang telah diputuskan dan mengadopsinya, membuatnya siap untuk round berikutnya.

Cloudflare mengakui bahwa ini disengaja: jika ada keputusan dalam fase sebelumnya, mayoritas perekam akan memiliki usulan tersebut, dan pembawa usulan yang tersisa dijamin mengadopsinya. Sifat kerjasama ini berarti setiap round berikutnya semakin mudah mencapai keputusan. Kertas QuePaxa memperkirakan setiap round memiliki peluang 50 persen untuk memutuskan, dan dalam praktiknya terjadi peningkatan bertahap.

Semua fase menggabungkan dirinya menjadi satu protokol: fase awal memberikan pemimpin jalur cepat satu perjalanan pulas. Jika jalur cepat gagal, prioritas acak dan adopsi usulan membantu pembawa usulan bersatu, bukan berkompetisi. Fase dua dan tiga menjaga keamanan keputusan berkat interseksi mayoritas, sementara fase keempat membawa hasil pelajaran ke round berikutnya.

Tidak ada pembawa usulan yang harus mendeteksi kegagalan pemimpin sebelum melanjutkan, dan satu round gagal tidak membuang pekerjaan yang telah dilakukan. Ketika jaringan berperilaku, QuePaxa cepat. Ketika jaringan tidak, QuePaxa terus bergerak.

Dalam evaluasi internal Meerkat, dengan server tersebar di hampir semua benua, Cloudflare langsung mengamati dampak QuePaxa terhadap performa dan ketersediaan sistem. Meerkat terus memproses permintaan meskipun pemimpin gagal, terputus, atau hanya lambat. Ia tidak pernah benar-benar berhenti.

Kinerja permintaan juga cenderung dapat diprediksi. Sebagian besar keputusan, di atas 95 persen, dilakukan oleh pemimpin pada fase awal, menjaga throughput yang stabil. Dalam kasus di mana keputusan tidak tercapai dalam fase awal, throughputnya turun sementara hingga maksimum sepertiga dari laju biasa, menandakan tiga perjalanan pulas atau tiga fase.

QuePaxa juga memungkinkan Cloudflare beralih replika yang bertindak sebagai pemimpin saat cluster berjalan. Karena pemimpin bukan pendorong eksklusif di belakang keputusan, dan pembawa usulan bekerja sama, pemimpin yang sementara tidak optimal tidak membatasi sistem seburuk konfigurasi pemimpin yang salah pada algoritma lainnya. Cloudflare dapat menyesuaikan dinamis mana yang menjadi pemimpin.

Merancang Meerkat untuk jaringan global memaksa Cloudflare untuk meninjau bagaimana pendekatan konsensus dilakukan. Alih-alih berpegang pada nilai default yang tidak cocok dengan keterbatasannya, perusahaan mencari protokol yang dirancang untuk lingkungan asinkron, yang tidak bergantung pada jaringan yang baik atau ketepatan waktu yang presisi.

Mempilih QuePaxa berarti memilih jalur yang kurang pernah dilalui. Protokol ini belum diuji dengan tantangan sebanyak Raft atau Paxos, dan Cloudflare juga memperpanjang desain crash-stop asli untuk mendukung pemulihan crash. Hal ini menuntut rekayasa hati-hati dan bukti kebenaran yang lebih kuat dari biasanya.

Karena itu, Cloudflare memverifikasi implementasi QuePaxa dan Meerkat secara formal, bersama dengan simulasi luas dan pengujian injeksi kegagalan. Posting berikutnya akan menjelaskan bagaimana verifikasi dilakukan, bagaimana pengujian kegagalan yang sulit direproduksi, serta benchmark dan pelajaran yang diperoleh saat mengubah protokol akademik menjadi produksi.

Manfaat QuePaxa adalah kunci untuk rekayasa jaringan global yang lebih kokoh. Cloudflare menawarkan protokol yang kuat di mana kecepatan sangat tergantung pada ketahanan jaringan yang relatif tidak dapat diprediksi. Dengan memproses permintaan terus-menerus, tanpa berhenti, sistem mendekati inisiatif yang sesuai dengan ekosistem modern.

Perbandingan antara dua pendekatan menunjukkan bagaimana teknologi yang kurang dikenal dapat menjadi pilihan yang rasional ketika kebutuhan teknis mengubah batas-batas yang biasanya. Di Cloudflare, QuePaxa menggantikan impulsif untuk memilih protokol yang kompatibel dengan jaringan global mereka. Spesifikasi algoritma memberikan jaminan yang memungkinkan sistem mengeksekusi dengan aman, menjaga replikasi dari konflik.