Pemilihan Pemimpin dalam Sistem Terdistribusi

Pemilihan pemimpin adalah ide sederhana untuk memberikan beberapa kekuatan khusus kepada sesuatu (proses, host, thread, objek, atau manusia) dalam sistem terdistribusi. Kekuatan khusus tersebut dapat mencakup kemampuan untuk menetapkan pekerjaan, kemampuan untuk memodifikasi sepotong data, atau bahkan tanggung jawab menangani semua permintaan dalam sistem.

Pemilihan pemimpin adalah alat yang ampuh untuk meningkatkan efisiensi, mengurangi koordinasi, menyederhanakan arsitektur, dan mengurangi operasi. Di sisi lain, pemilihan pemimpin dapat memperkenalkan mode kegagalan baru dan menskalakan kemacetan. Selain itu, pemilihan pemimpin dapat mempersulit Anda untuk mengevaluasi kebenaran suatu sistem.

Karena kerumitan ini, kami mempertimbangkan opsi lain dengan cermat sebelum menerapkan pemilihan pemimpin. Untuk pemrosesan data dan alur kerja, layanan alur kerja seperti AWS Step Functions dapat memperoleh banyak keuntungan yang sama seperti pemilihan pemimpin dan menghindari risikonya. Untuk sistem lain, kami sering mengimplementasikan API idempoten, penguncian optimis, dan pola lain yang membuat seorang pemimpin tunggal tidak diperlukan.

Dalam artikel ini, saya membahas beberapa pro dan kontra pemilihan pemimpin secara umum dan bagaimana Amazon mendekati pemilihan pemimpin dalam sistem terdistribusi kami, termasuk wawasan tentang kegagalan pemimpin.

Ada banyak cara untuk memilih pemimpin, mulai dari algoritme seperti Paxos, hingga perangkat lunak seperti Apache ZooKeeper, perangkat keras khusus, hingga sewa. Sewa adalah mekanisme pemilihan pemimpin yang paling banyak digunakan di Amazon. Sewa relatif mudah dipahami dan diterapkan, dan mereka menawarkan toleransi kesalahan bawaan. Sewa bekerja dengan memiliki satu database yang menyimpan pemimpin saat ini. Kemudian, perjanjian sewa mensyaratkan bahwa pemimpinberfungsisecara berkala menunjukkan bahwa ia masih menjadi pemimpin. Jika pemimpin yang ada gagal berfungsi setelah beberapa waktu, kandidat pemimpin lain dapat mencoba mengambil alih.

Kami menghindari bergantung pada waktu sistem yang terdistribusi, bahkan dengan fitur sinkronisasi waktu terbaik di Amazon Elastic Compute Cloud (Amazon EC2). Sulit untuk memastikan bahwa jam sistem di seluruh klaster cukup disinkronkan untuk bergantung pada sinkronisasi dalam memesan atau mengoordinasikan operasi yang didistribusikan. Di Amazon, sistem terdistribusi hanya menggunakan waktu untuk konsumsi manusia. Sewa bergantung pada waktu. Namun, mereka hanya bergantung pada durasi waktu lokal yang berlalu, bukan waktu jam dinding yang disinkronkan dan perlu disepakati oleh beberapa server.

Kode sumber klien penguncian DynamoDB menawarkan contoh dan detail terkait pemilihan pemimpin. Namun, kami telah menemukan bahwa, meskipun sewa dan penguncian secara konsep sederhana, implementasi yang benar dapat menjadi rumit. Implementasi membutuhkan pemahaman tentang cara server mengukur durasi waktu lokal. Misalnya, jika server atau pustaka yang mengukur waktu berpikir bahwa waktu melonjak sesekali, hal ini akan mematahkan asumsi tentang durasi waktu yang dibangun dalam sewa. Durasi menghindari masalah dengan sinkronisasi jam global yang menyebabkan server berhenti menyetujui pada jam berapa, dari detik lompatan hingga jam lokal melewati seiring waktu dari pemanfaatan CPU yang tinggi secara berkelanjutan.

Masalah yang lebih besar untuk sewa, dan semua jenis kunci yang didistribusikan, memastikan bahwa pemimpin hanya melakukan pekerjaan saat memegang kunci. Memastikan bahwa pemimpin memegang kunci sebenarnya cukup sulit. Kami merasa penting untuk memastikan bahwa pemimpin di jaringan yang lambat atau hilang tidak meyakini bahwa mereka memegang kunci lebih lama dari yang sebenarnya. Demikian pula, pengumpulan sampah yang berhenti di antara kunci yang diperiksa dan pekerjaan yang dilakukan dapat menyebabkan perilaku yang salah. Dalam praktiknya, penegasan terhadap masalah-masalah ini seringkali merupakan tantangan terbesar.

DynamoDB dan ZooKeeper menawarkan klien penguncian berbasis sewa sederhana yang memberikan pemilihan pemimpin yang toleran terhadap kesalahan. Kecuali terdapat kebutuhan khusus, kami lebih suka klien ini karena menurut kami mereka memberikan cara termudah dan paling teruji untuk menerapkan pemilihan pemimpin. Tim Amazon lebih memilih untuk menghindari menciptakan implementasi pemilihan pemimpin khusus. Sebagai gantinya, kami lebih menyukai klien yang sudah ada, teruji, dan berjuang keras.

Pemilihan pemimpin adalah pola yang digunakan secara luas di seluruh Amazon. Misalnya:

• Hampir semua sistem yang menggunakan sistem manajemen databse relasional tradisional (RDBMS) mengandalkan pemilihan pemimpin untuk memilih database pemimpin yang menangani semua penulisan, dan kadang-kadang, semua dapat membaca. Dalam sistem ini, pemilihan mungkin dilakukan secara otomatis, tetapi sering dilakukan secara manual oleh operator manusia.
• Amazon EBS mendistribusikan pembacaan dan penulisan volume di banyak server penyimpanan. Untuk memastikan konsistensi, Amazon EBS menggunakan pemilihan pemimpin untuk memilih yang primer pada setiap area volume, yang memesan pembacaan dan penulisan. Jika yang primer gagal, pengikut menyalin langkah-langkah dalam menggunakan mekanisme pemilihan pemimpin yang sama. Di Amazon EBS, pemilihan pemimpin memastikan konsistensi, sambil meningkatkan kinerja dengan menghindari koordinasi pada bidang data. DynamoDB, Amazon Quantum Ledger Database (Amazon QLDB), dan Amazon Kinesis (Kinesis) menggunakan pendekatan serupa untuk alasan yang sama.
• Kinesis Client Library (KCL) menggunakan sewa untuk memastikan bahwa setiap bagian Kinesis diproses oleh satu pemilik, sehingga memudahkan untuk melakukan pemrosesan skala besar terhadap aliran Kinesis.

Hal lain yang harus dipikirkan dengan hati-hati adalah apa yang terjadi pada pekerjaan pemimpin ketika gagal. Jika pemimpin gagal selama tugas, bagaimana pemimpin baru menyelesaikan tugas? Jika pemimpin gagal sebelum membuat pekerjaannya dapat tahan lama, apakah sistem masih benar? Banyak jenis sistem memiliki langkah “buat pekerjaan yang tahan lama” terpisah dan “beri tahu orang lain bahwa ini sudah lengkap”. Amazon, sistem kami selalu melakukan yang paling awal sebelum yang terakhir (atau menoleransi kehilangan data). Sekali lagi, idempotensi berguna di sini. Hal ini memungkinkan pemimpin baru untuk percaya diri mengembangkan kembali pekerjaan yang mungkin telah selesai sebagian atau selesai oleh pemimpin sebelumnya tetapi tidak memberi tahu orang lain.

Untuk menoleransi kegagalan, sistem yang didistribusikan Amazon tidak memiliki pemimpin tunggal. Sebaliknya, kepemimpinan adalah properti yang berpindah dari server ke server, atau proses ke proses. Dalam sistem terdistribusi, tidak mungkin untuk menjamin bahwa ada tepat satu pemimpin dalam sistem. Sebagai gantinya, sebagian besar bisa ada satu pemimpin, dan bisa ada nol pemimpin atau dua pemimpin selama kegagalan.

Cara kami memilih perilaku sistem pada kegagalan pemimpin tergantung apa yang terjadi dalam suatu sistem ketika ada dua pemimpin. Sistem yang melakukan pekerjaan yang idempoten sering dapat menoleransi dua pemimpin dengan kehilangan efisiensi minimal. Dengan dua pemimpin, sistem dapat mencapai ketersediaan yang lebih tinggi dan memilih pendekatan pemilihan pemimpin yang lebih lemah.

Sistem yang benar-benar membutuhkan paling banyak satu pemimpin lebih sulit dibangun daripada banyak sistem pemimpin. Sistem pemilihan pemimpin harus selalu benar dan konsisten. Selain itu, pemimpin harus memastikan bahwa pemimpin yang sebelumnya telah turun sebelum pemimpin baru terpilih, yang lebih sulit daripada yang terlihat. Dalam sistem terdistribusi, seringkali sulit untuk mengetahui apakah suatu sistem telah gagal atau apakah sistem hanya terus bekerja di beberapa partisi jaringan lain. Di Amazon, kami memastikan bahwa sistem yang dipilih pemimpin menangani kasus edge ini.

Di Amazon, kami mengikuti praktik terbaik ini untuk pemilihan pemimpin:

• Periksa sisa waktu sewa (atau mengunci status secara umum) secara rutin, dan terutama sebelum memulai operasi yang memiliki efek samping di luar pemimpin itu sendiri.
• Pertimbangkan bahwa jaringan yang lambat, batas waktu, percobaan ulang, dan pengumpulan sampah dijeda dapat menyebabkan sisa waktu sewa berakhir sebelum yang diperkirakan kode.
• Hindari sewa yang masih berfungsi di thread latar belakang. Hal ini dapat menyebabkan masalah kebenaran jika thread tidak dapat mengganggu kode ketika masa sewa habis atau thread yang berfungsi mati. Masalah ketersediaan dapat terjadi jika thread kerja mati atau berhenti saat thread yang berfungsi bertahan untuk menyewa.
• Memiliki metrik yang dapat diandalkan yang menunjukkan seberapa banyak pekerjaan yang dapat dilakukan pemimpin dibanding seberapa banyak yang dilakukannya sekarang. Tinjau metrik ini sesering mungkin, dan pastikan ada rencana penskalaan sebelum kehabisan kapasitas.
• Buatlah mudah untuk menemukan host mana yang merupakan pemimpin saat ini dan host mana yang menjadi pemimpin pada waktu tertentu. Menyimpan jejak audit atau catatan perubahan kepemimpinan.
• Buat model dan secara formal verifikasi kebenaran algoritme terdistribusi menggunakan alat seperti TLA+. Hal ini menangkap bug yang halus, sulit untuk diamati, dan langka yang dapat menyusup ketika aplikasi mengasumsikan terlalu banyak tentang jaminan yang diberikan oleh protokol pemilihan pemimpin.

Pemilihan pemimpin adalah alat yang ampuh yang digunakan dalam sistem di seluruh Amazon untuk membantu membuat sistem kami toleran terhadap kesalahan dan lebih mudah dioperasikan. Namun, ketika kami menggunakan pemilihan pemimpin, kami berhati-hati untuk mempertimbangkan jaminan yang diberikan oleh setiap protokol pemilihan pemimpin, dan yang lebih penting, tidak memberikan.

Sistem Amazon seringkali menggunakan pemilihan pemimpin untuk memastikan terdapat toleransi terhadap kegagalan bawaan. Ketika sistem menggunakan pemilihan pemimpin untuk memastikan bahwa setidaknya satu server memproses tugas, mereka menggunakan mekanisme terpisah untuk menjaga kebenaran dalam menghadapi beberapa pemimpin bersamaan. Misalnya, mereka mungkin menggunakan database yang mendasari untuk memastikan bahwa jika dua pemimpin berpikir mereka berdua memegang kontrak, mereka tidak saling mengganggu. Daripada membuat asumsi tentang jaminan yang diberikan oleh implementasi penyewa, kami fokus pada kebenaran dalam sistem ini, seringkali dengan pemodelan dengan teknik seperti TLA+.

Di luar kondisinya, pemilihan pemimpin tetap menjadi alat yang berguna dalam toolkit sistem terdistribusi kami di Amazon, di samping pola seperti idempotensi dan penguncian optimis.

Untuk informasi selengkapnya mengenai cara kerja sewa, lihat:

• Cara melakukan penguncian terdistribusi
• Burrows, Layanan penguncian Chubby untuk sistem terdistribusi secara longgar
• Gray and Cheriton, Sewa: Mekanisme Toleransi Kesalahan yang Efisien untuk Konsistensi Cache File Terdistribusi