Pemilihan Simpul Utama di Sistem Terdistribusi

Pemilihan simpul utama adalah ide sederhana untuk memberikan satu entitas (proses, host, thread, objek, atau manusia) dalam sistem terdistribusi agar memiliki hak istimewa khusus. 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 terhadap pemilihan simpul utama secara umum dan cara Amazon menerapkan pemilihan simpul utama dalam sistem terdistribusi kami, termasuk wawasan tentang kegagalan simpul utama.

Pemilihan pemimpin adalah pola umum dalam sistem terdistribusi karena memiliki beberapa keuntungan signifikan:

• Pemimpin tunggal membuat sistem lebih mudah bagi manusia untuk dipikirkan. Hal ini menempatkan semua konkurensi dalam sistem menjadi satu tempat, mengurangi mode kegagalan sebagian, dan menambahkan satu tempat untuk mencari log dan metrik.
• Pemimpin tunggal dapat bekerja lebih efisien. Pemimpin tunggal seringkali dapat dengan mudah memberi tahu sistem lain tentang perubahan, daripada membangun konsensus tentang perubahan yang akan dibuat.
• Pemimpin tunggal dapat dengan mudah menawarkan konsistensi klien karena mereka dapat melihat dan mengendalikan semua perubahan yang dibuat untuk status sistem.
• Dengan satu simpul utama, performa dapat ditingkatkan atau biaya dapat diturunkan melalui penyediaan satu cache data yang konsisten yang dapat digunakan setiap saat.
• Menulis perangkat lunak untuk satu simpul utama mungkin lebih mudah daripada pendekatan lain seperti kuorum. Dengan satu simpul utama, tidak perlu mempertimbangkan bahwa sistem lain dapat mengakses keadaan yang sama pada waktu yang sama.

Pemilihan pemimpin juga memiliki beberapa kerugian besar:

• Pemimpin tunggal adalah titik kegagalan tunggal. Jika sistem gagal mendeteksi atau memperbaiki pemimpin yang buruk, seluruh sistem dapat tidak tersedia.
• Pemimpin berarti satu titik penskalaan, baik dalam ukuran data dan tingkat permintaan. Ketika sebuah sistem yang dipilih oleh pemimpin perlu tumbuh melampaui pemimpin, ia membutuhkan arsitektur ulang yang lengkap.
• Pemimpin merupakan titik kepercayaan tunggal. Jika pemimpin melakukan pekerjaan yang salah tanpa ada yang memeriksanya, hal ini dapat dengan cepat menyebabkan masalah di seluruh sistem. Pemimpin yang buruk memiliki blast radius yang tinggi.
• Penerapan sebagian mungkin sulit diterapkan dalam sistem pemimpin yang dipilih. Banyak praktik keamanan perangkat lunak di Amazon bergantung pada penerapan parsial, seperti pengujian satu kotak, A-B, penerapan biru/hijau, dan penerapan tambahan dengan rollback otomatis.

Banyak dari kerugian ini dapat dikurangi dengan berhati-hati memilih ruang lingkup pemimpin. Seberapa besar sistem atau data yang dimiliki pemimpin? Pola umum di sini adalah sharding. Setiap item data masih milik pemimpin tunggal, tetapi keseluruhan sistem berisi banyak pemimpin. Ini adalah pendekatan desain mendasar di balik Amazon DynamoDB (DynamoDB), Amazon Elastic Block Store (Amazon EBS), Amazon Elastic File System (Amazon EFS), dan banyak sistem lainnya di Amazon. Sharding memiliki kelemahannya sendiri. Secara khusus, terdapat kompleksitas desain yang lebih tinggi serta kebutuhan untuk memikirkan dengan cermat cara membagi data menjadi serpihan (shard).  

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. Lease bekerja menggunakan satu basis data yang menyimpan simpul utama saat ini. Kemudian, lease mengharuskan simpul utama untuk mengirimkan heartbeat secara berkala untuk menunjukkan bahwa simpul tersebut masih aktif menjadi simpul utama. Jika simpul utama tidak mengirimkan heartbeat setelah beberapa waktu, kandidat simpul utama 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. Lease bergantung pada waktu. Namun, lease hanya bergantung pada durasi waktu lokal yang berlalu, bukan waktu global yang disinkronkan dan perlu disepakati oleh beberapa server.

Kode sumber klien penguncian DynamoDB menawarkan contoh dan detail terkait pemilihan simpul utama. 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.

Contoh sistem menggunakan pemilihan pemimpin di Amazon

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

• Hampir semua sistem yang menggunakan sistem manajemen basis data relasional (RDBMS) tradisional mengandalkan pemilihan simpul utama untuk memilih basis data utama yang menangani semua operasi tulis, dan terkadang juga semua operasi baca. 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.
• Pustaka Klien Kinesis (KCL) menggunakan lease untuk memastikan bahwa setiap serpihan (shard) Kinesis diproses oleh satu pemilik sehingga memudahkan untuk melakukan pemrosesan aliran Kinesis dalam skala besar.
  

Hal lain yang harus dipertimbangkan dengan hati-hati adalah apa yang terjadi pada pekerjaan simpul utama saat terjadi kegagalan. 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 simpul utama dapat 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. Simpan jejak audit atau log perubahan kepemimpinan simpul utama.
• Buat model dan verifikasi kebenaran algoritma terdistribusi secara formal menggunakan alat seperti TLA+. Hal ini dapat membantu mendeteksi bug yang halus, sulit diamati, dan jarang terjadi yang dapat muncul ketika aplikasi membuat asumsi berlebihan tentang jaminan yang diberikan oleh protokol pemilihan simpul utama.  

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+.

Terlepas dari berbagai kompleksitasnya, pemilihan simpul utama tetap menjadi alat yang berguna dalam kit alat sistem terdistribusi kami di Amazon, bersama dengan pola seperti idempotensi dan penguncian optimis.

Untuk informasi selengkapnya mengenai cara kerja lease, lihat:

• Cara melakukan penguncian terdistribusi
• Burrows, Layanan penguncian Chubby untuk sistem terdistribusi yang tidak saling bergantung
• Gray dan Cheriton, Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency