Algoritme Konsensus Raft (2015)
(raft.github.io)- Raft dirancang untuk menjelaskan masalah konsensus—membuat beberapa server dalam sistem terdistribusi mengambil keputusan yang sama—dengan cara yang lebih mudah dipahami, dengan target toleransi kesalahan dan performa yang setara dengan Paxos
- Raft membagi struktur ke dalam submasalah seperti pemilihan leader, replikasi log, dan keselamatan, sehingga titik-titik keputusan yang diperlukan untuk mengimplementasikan replicated state machine menjadi jelas
- Selama mayoritas server masih hidup, sistem dapat terus berjalan; jika mayoritas hilang, sistem berhenti tetapi tetap menjaga keselamatan dengan tidak menghasilkan hasil yang salah
- Situs ini mengumpulkan visualisasi berbasis browser RaftScope dan The Secret Lives of Data, makalah Raft, spesifikasi TLA+, makalah verifikasi dan analisis, serta materi presentasi
- Tersedia daftar implementasi dalam berbagai bahasa seperti Rust, Go, Java, C++, C#, dan Python; cakupan dukungan untuk pemilihan leader, replikasi log, persistensi, perubahan keanggotaan, dan kompaksi log berbeda-beda pada tiap implementasi
Masalah konsensus yang dibidik Raft
- Raft dirancang agar algoritme konsensus dapat dipahami oleh kalangan pembaca yang lebih luas
- Toleransi kesalahan dan performanya menargetkan tingkat yang setara dengan Paxos
- Perbedaan utamanya ada pada struktur
- Masalah dipecah menjadi submasalah yang relatif independen
- Komponen yang diperlukan untuk implementasi sistem nyata dipisahkan dan dibahas secara tersendiri
- Tujuannya adalah membuat sistem berbasis konsensus lebih mudah dipahami dan dapat diimplementasikan dengan kualitas yang lebih tinggi
Konsensus dan replicated state machine
- Konsensus (consensus) adalah masalah dasar dalam sistem terdistribusi yang toleran terhadap kesalahan
- Beberapa server menyepakati satu nilai, dan nilai yang sudah diputuskan menjadi keadaan final
- Algoritme konsensus umumnya dapat berjalan ketika mayoritas server tersedia
- Klaster dengan 5 server dapat terus beroperasi meski 2 server gagal
- Jika lebih banyak server gagal, proses akan berhenti
- Yang penting, dalam kondisi ini sistem tetap tidak mengembalikan hasil yang salah
- Konsensus biasanya digunakan untuk membuat replicated state machine
- Setiap server memiliki state machine dan log
- State machine dapat berupa komponen yang ingin diberi toleransi kesalahan, misalnya tabel hash
- Klien dapat melihatnya seolah-olah berinteraksi dengan satu state machine tepercaya meski sebagian server gagal
- Setiap state machine menerima perintah sebagai input dari log miliknya
- Dalam contoh tabel hash, perintah seperti
set x to 3masuk ke dalam log - Algoritme konsensus menentukan perintah apa yang dimasukkan ke log server dan dalam urutan apa
- Jika satu state machine menerapkan
set x to 3sebagai perintah ke-n, algoritme harus menjamin state machine lain tidak menerapkan perintah berbeda pada posisi yang sama
- Dalam contoh tabel hash, perintah seperti
- Akibatnya, semua state machine memproses urutan perintah yang sama dan mencapai urutan hasil serta urutan keadaan yang sama
Visualisasi untuk memahami Raft
- Anda dapat langsung mengoperasikan visualisasi klaster Raft yang berjalan di browser
- Di sisi kiri ditampilkan 5 server
- Di sisi kanan ditampilkan log masing-masing server
- Pengguna dapat melihat cara kerja Raft melalui interaksi
- RaftScope masih memiliki banyak bagian yang perlu dipoles dan menerima Pull Request
- The Secret Lives of Data adalah visualisasi yang menampilkan Raft dengan cara berbeda
- Lebih terpandu dan interaksinya lebih sedikit
- Dapat menjadi titik awal yang lebih mulus bagi pembaca yang baru pertama kali mengenalnya
Makalah, spesifikasi, dan materi verifikasi
- In Search of an Understandable Consensus Algorithm (Extended Version) adalah “makalah Raft” yang membahas Raft secara rinci
- Ditulis oleh Diego Ongaro dan John Ousterhout
- Versi yang sedikit lebih pendek menerima Best Paper Award di 2014 USENIX Annual Technical Conference
- Disertasi Ph.D. Diego Ongaro memperluas isi makalah secara lebih mendalam
- Mencakup algoritme perubahan keanggotaan klaster yang lebih sederhana
- Juga memuat spesifikasi formal TLA+ untuk Raft
- Spesifikasi yang sedikit diperbarui dapat dilihat di raft.tla
- Makalah terkait membahas verifikasi formal Raft, framework implementasi dan verifikasi sistem terdistribusi, pembuatan kode berbasis model formal, serta analisis protokol
- Planning for Change in a Formal Verification of the Raft Consensus Protocol, CPP 2016
- Verdi: A Framework for Implementing and Verifying Distributed Systems, PLDI 2015
- Automatic Distributed Code Generation from Formal Models of Asynchronous Concurrent Processes, PDP 2015
- Raft Refloated: Do We Have Consensus?, SIGOPS Operating Systems Review 2015
- ARC: Analysis of Raft Consensus, University of Cambridge Technical Report 2014
Presentasi dan materi pendidikan
- Daftar presentasi pengantar Raft juga dikumpulkan di sini
- Presentasi John Ousterhout dalam CS@Illinois Distinguished Lecture Series, Agustus 2016
- Presentasi Jin Li tentang Raft dan spesifikasi TLA+ dalam Dr. TLA+ Series, Juli 2016
- Presentasi Diego Ongaro di Build Stuff 2015, CoreOS Fest 2015, meetup Sourcegraph, LinkedIn, USENIX ATC 2014, CraftConf 2014, dan RICON West 2013
- Presentasi Ben Johnson di Strange Loop 2013
- Kuliah Raft User Study oleh John Ousterhout, Maret 2013
- Raft juga digunakan dalam perkuliahan atau tugas pemrograman di universitas dan program pendidikan
- Termasuk berbagai mata kuliah di University of Copenhagen, Czech Technical University in Prague, The University of Hong Kong, University of Virginia, UC San Diego, Technical University of Munich, UIUC, dan lainnya
- Beberapa mata kuliah menyediakan tugas pemrograman Raft dalam Go, Java, Erlang, dan lainnya
- MIT 6.824 menyertakan catatan kuliah Raft, serta mengarahkan ke tulisan Raft Jon Gjengset untuk pengajar dan mahasiswa
- Mata kuliah tambahan dapat diperbarui melalui Pull Request atau issue di repositori situs
Kanal pertanyaan dan daftar implementasi
- Untuk pertanyaan tentang Raft dan implementasinya, Google group raft-dev diarahkan sebagai tempat yang sesuai
- Sebagian implementasi memiliki mailing list sendiri, sehingga README masing-masing perlu diperiksa
- Situs ini juga menyediakan daftar implementasi Raft yang memiliki kode sumber publik
- Implementasi yang populer atau baru-baru ini diperbarui ditempatkan di bagian atas tabel
- Informasi dapat menjadi usang seiring waktu, sehingga dapat diperbarui melalui Pull Request atau issue
- Tabel membandingkan Stars, nama, penulis utama, bahasa, lisensi, dan dukungan fitur untuk tiap implementasi
- Item fitur mencakup pemilihan leader dan replikasi log, persistensi, perubahan keanggotaan, serta kompaksi log
- Contoh implementasi teratas adalah sebagai berikut
- TiKV: Rust, Apache-2.0, 16.751★, mendukung semua fitur utama: pemilihan leader dan replikasi log/persistensi/perubahan keanggotaan/kompaksi log
- RethinkDB: C++, Apache-2.0, 27.000★, mendukung semua fitur utama
- Seastar Raft: C++20, AGPL, 15.624★, mendukung semua fitur utama
- hashicorp/raft: Go, MPL-2.0, 9.048★, mendukung semua fitur utama
- hazelcast-raft: Java, Apache-2.0, 6.579★, mendukung semua fitur utama
- Daftar ini mencakup implementasi dalam berbagai bahasa seperti Rust, Go, Java, C++, C, Erlang, Python, Scala, C#, JavaScript, Haskell, OCaml, Kotlin, Zig, TypeScript, Elixir, F#, dan Shell
1 komentar
Opini Hacker News
Maelstrom, workbench untuk mempelajari sistem terdistribusi dari pembuat Jepsen, berisi implementasi verifikasi model Raft yang sederhana serta tutorial implementasinya dengan baik: https://github.com/jepsen-io/maelstrom/
Raft adalah algoritme yang sederhana, tetapi makalah aslinya memuat banyak detail kebenaran yang sering dihilangkan dalam implementasi mainan
Jika ikut mempertimbangkan korupsi memori/disk pada hardware nyata, grey failure, SLA latensi yang ketat, kuorum fleksibel, dan keanggotaan klaster dinamis, implementasi produksi menjadi pekerjaan yang panjang dan membebani
Melihat riwayat commit etcd dan hashicorp/raft saja sudah cukup untuk mengetahui bahwa bahkan implementasi Raft open source yang paling banyak diverifikasi pun secara berkala masih memunculkan bug kebenaran
Tim TigerBeetle membahas secara rinci realitas sistem terdistribusi pada hardware yang tidak sempurna dan model sistem yang tidak diabstraksikan, serta menjelaskan mengapa mereka memilih Viewstamped Replication, yang lebih tua daripada Paxos tetapi tampak lebih mirip Raft: https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/DE...
Saya tidak begitu tahu apa implikasinya terhadap pertimbangan implementasi, tetapi makalahnya sendiri bagus, jadi saya ingin merekomendasikannya
Ada juga presentasinya, tetapi menurut saya tulisan lebih baik untuk dibaca sambil bolak-balik merujuk bagian-bagiannya: https://www.youtube.com/watch?v=0K6kt39wyH0
Meski sebelumnya sama sekali belum pernah melihat algoritme konsensus, setelah membacanya beberapa kali saya bisa mengikutinya sampai tingkat tertentu: https://dspace.mit.edu/bitstream/handle/1721.1/71763/MIT-CSA...
Baru-baru ini saya mencoba mengimplementasikan pemilihan leader dan replikasi log pada Raft. Saya belum sampai ke snapshot/checkpoint, tetapi ini termasuk salah satu proyek tersulit yang pernah saya kerjakan
Makalah Raft mudah dibaca dan memberi intuisi yang bagus
Sekalipun tidak mengimplementasikannya sendiri, besar kemungkinan Anda sudah memakai software berbasis Raft seperti etcd, Consul, CockroachDB, atau TiDB
Materi yang berguna saat implementasi saya kumpulkan di sini: https://github.com/eatonphil/goraft#references
Termasuk disertasi doktoral Diego Ongaro dan spesifikasi TLA+
Ada yang mengatakan “Figure 2 di makalah Raft saja sudah cukup”, tetapi dibandingkan dengan spesifikasi TLA+ itu jauh lebih ambigu, jadi menurut saya itu tidak benar
Saya menyarankan untuk menghubungkannya dengan tes Raft dari kuliah sistem terdistribusi MIT: https://pdos.csail.mit.edu/6.824/labs/lab-raft.html
Setidaknya untuk bagian pemilihan leader dan replikasi log, tampaknya bisa dilakukan hanya dengan sedikit refactoring
Terutama bagi orang yang baru pertama kali bersentuhan dengan algoritme terdistribusi, ini benar-benar layak direkomendasikan
Kualitas implementasinya mungkin tidak luar biasa, tetapi saya unggah untuk siapa pun yang tertarik: https://github.com/skowalak/fastapi-raft/
Ada beberapa detail konkret lain di dalam makalah yang dibutuhkan saat implementasi
Jika tertarik pada algoritme konsensus, buku Reasoning about Knowledge yang dipakai di kelas teori sistem terdistribusi juga layak dilihat: https://mitpress.mit.edu/9780262562003/reasoning-about-knowl...
Perlu sedikit investasi untuk mempelajari logika modal, tetapi setelah melewati bagian itu, pembuktian mengapa Raft atau Paxos bekerja menjadi sangat intuitif dan sederhana
Pendekatannya adalah mendorong kompleksitas pembuktian ke dalam struktur logika yang dipakai untuk pembuktian, dan itu mengubah cara saya memandang konsensus
“Raft Consensus Algorithm Failure”, Théodore Géricault, 1819: https://classicprogrammerpaintings.com/post/6141087496359280...
Jika tidak tahu apa yang ditampilkan visualisasi itu, perhatikan bahwa Anda bisa mengeklik salah satu node untuk membuatnya mengalami kegagalan
Terutama bagus jika dicoba pada node yang saat ini menjadi leader, yang mengirim dan menerima semua paket
Jika menekan ikon jeda kecil di sebelah slider pertama untuk mengubahnya kembali menjadi jam, simulasi akan dilanjutkan
Saya masih belum tahu spreadsheet di sebelah kanan itu apa, dan karena selalu kosong, terlihat seperti rusak
Elemen yang bisa diklik yang sejauh ini saya temukan adalah dua slider, ikon jam/jeda, dan masing-masing server
Jika mengeklik leader dan memilih
request, Anda bisa menyimulasikan pengiriman perintahJika satu replika dibuat offline, Anda bisa melihatnya tertinggal lalu mengejar ketertinggalannya saat kembali online
Beberapa tahun lalu, saya berada di lingkungan yang selalu membutuhkan sistem mirip Chubby yang tangguh di bawah beban serius, dan saat itu jika kegagalan tidak bisa ditoleransi, kami memakai ZooKeeper
Namun sekarang saya tahu orang-orang sudah bertahun-tahun menjalankan beban kerja yang sangat berat di atas opsi berbasis Raft seperti etcd dan Consul
Saya penasaran apakah salah satu dari ini sekarang sudah menjadi pilihan default
Kejelasan konseptual dan keanggunan Raft terasa seharusnya berujung pada performa dan keandalan, tetapi insting saya di bidang ini sudah ketinggalan zaman
Saya penasaran, pada 2023, orang-orang yang tidak terikat pada Google atau GCP memakai apa sebagai praktik terbaik default untuk sistem dengan tingkat kepentingan tinggi
Seingat saya ada implementasi Raft Rust kelas produksi yang dibuat oleh pihak TikV, dan server lock yang tangguh serta berperforma tinggi tampak seperti ranah yang cukup cocok untuk Rust; saya juga penasaran apakah itu benar-benar dipakai
Kalau ini jawaban untuk “Apa itu Raft?”, setelah membacanya saya masih tetap tidak tahu
“Raft adalah algoritma konsensus yang dirancang agar mudah dipahami. Dalam hal toleransi kegagalan dan performa, Raft setara dengan Paxos. Perbedaannya adalah Raft dipecah menjadi submasalah yang relatif independen, dan menangani bagian-bagian utama yang diperlukan untuk sistem praktis dengan rapi. Kami berharap Raft dapat membuat konsensus tersedia bagi pembaca yang lebih luas, dan agar pembaca itu dapat membangun sistem berbasis konsensus berkualitas tinggi yang lebih beragam daripada saat ini”
Hal seperti ini bukan hanya masalah mereka, tetapi menurut saya sayang sekali mereka tidak meluangkan lebih banyak waktu untuk menjelaskan pekerjaan mereka sendiri dengan benar
Karena secara otomatis menyaring pembaca yang tidak memahami maknanya
Bagi orang yang membangun sistem terdistribusi dan membandingkan beberapa algoritma konsensus, ini penjelasan yang sederhana dan jelas; kalau tidak, kemungkinan besar algoritma itu memang tidak relevan bagi mereka
Secara umum, algoritma konsensus berusaha memecahkan masalah ketika ada replika penyimpanan data yang tersebar di beberapa perangkat fisik, dan harus menentukan apa yang dilakukan saat sebagian perangkat atau koneksi gagal dengan cara tertentu
Disebut “konsensus” karena dalam situasi kegagalan, mesin-mesin harus mencapai kesepakatan tentang keputusan apa yang diambil terhadap potongan data
Misalnya, jika ada tiga server yang mereplikasi database SQL yang sama dalam bentuk
(A) - (B) - (C), lalu koneksi jaringan antara C dan dua server lainnya terputus, A dan B bisa mengetahui hal itu dan mempromosikan B menjadi node utamaNamun C tidak tahu apa yang terjadi dan bisa terus menerima sebagian penulisan
Ketika koneksi pulih, A, B, dan C sekarang harus memutuskan apa yang akan dilakukan
Karena B dan C telah menerima kumpulan penulisan yang berbeda secara independen, server-server itu harus menyepakati cara menangani data
Inilah masalah yang ingin diselesaikan Raft, Paxos, dan lainnya secara konsisten dan berkinerja baik
Ada konsep yang terlalu besar untuk diperkenalkan dalam satu paragraf kepada orang yang sama sekali tidak punya pengetahuan latar
Meski begitu, menurut saya tulisan yang ditautkan itu adalah materi pengantar yang bagus jika terus dibaca
Sebagai peneliti protokol konsensus, menurut saya berkat riset blockchain selama 10 tahun terakhir, konsensus menjadi jauh lebih mudah dipahami
Raft, terutama jika memasukkan bagian-bagian halusnya, dibandingkan itu terasa dan terimplementasi seperti bahasa Yunani
Jika ada orang yang baru mulai mempelajari protokol konsensus sekarang, saya mungkin akan menyuruhnya mulai dari Bitcoin lalu lanjut ke Paxos, Tendermint, Simplex, dan melewatkan Raft sama sekali
Simplex adalah paper yang saya tulis, versi sederhana dari PBFT
Raft tampak relatif sederhana
Saya penasaran apa yang ditawarkan blockchain sehingga lebih mudah dipelihara dan lebih sulit salah dibanding “memilih leader dan mereplikasi log”
Saya suka situs ini
Saat belajar dan mengimplementasikan Raft di kelas sistem terdistribusi, halaman ini sangat berguna
Paper-nya sendiri juga cukup mudah dibaca
Terima kasih sudah membuat Raft sejelas ini
Saya penasaran apakah ada algoritme konsensus yang perubahan tidak harus selalu melewati leader
Dalam banyak sistem terdistribusi, pemrosesan input juga ingin didistribusikan
Salah satunya adalah Chord: https://en.m.wikipedia.org/wiki/Chord_(peer-to-peer)
Chord adalah ring P2P tempat node membagi nilai dengan consistent hashing
Jaringannya memanfaatkan sesuatu yang disebut “finger table”, yang pada dasarnya menyimpan informasi replikasi dalam bentuk tabel
Informasi dalam tabel ini bisa salah atau usang, dan peer yang diakses dapat memberi tahu untuk pergi ke peer lain, biasanya node berikutnya atau node penerus, lalu proses berlanjut sampai nilainya ditemukan atau dinyatakan tidak ditemukan
Alasan algoritme ini bisa digunakan tanpa “leader” adalah karena ia tetap berfungsi meski hanya pergi ke satu node lalu menelusuri semua node secara linear
Finger table untuk mempercepat kueri tidak wajib
Sistem seperti ini biasanya memiliki “leader” untuk setiap transaksi, tetapi dalam operasi normal peran itu tidak diperebutkan
Koordinator transaksi mendeklarasikan dirinya sendiri, sehingga pemilihan hanya terjadi ketika koordinator gagal karena alasan tertentu
Untuk data atau key tertentu, beberapa leader juga bisa ada secara bersamaan
Cassandra saat ini sedang mengembangkan Accord, protokol tanpa leader dari keluarga ini
Sebenarnya Cassandra sudah menggunakan protokol tanpa leader untuk LWT
Itu adalah varian optimasi dari Paxos konsensus tunggal klasik, tetapi overhead-nya cukup besar jika transaksi yang bersaing untuk key yang sama dideklarasikan secara bersamaan
Jika transaksi tersebar pada topik-topik yang independen, beban dapat didistribusikan dengan melakukan sharding pada leader
Caranya adalah menetapkan rentang keyspace ke leader yang berbeda, lalu menyesuaikan pemilihan agar setiap node memiliki porsi leadership yang sesuai
Jika ingin berjalan tanpa leader, setiap penulisan pada dasarnya bisa disusun seperti sebuah pemilihan
Jika transaksi tentatif atau transaksinya besar, permintaan transaksi dapat di-broadcast ke semua node, lalu jika memperoleh kuorum penerimaan, transaksi menang dan di-commit
Namun jika beberapa node mencoba transaksi hampir bersamaan, mencapai konsensus bisa memakan banyak waktu
Jika ada banyak node dan semuanya memiliki transaksi tertunda untuk topik yang sama, memilih leader dan mengirim semua transaksi melalui leader jauh lebih cepat daripada membangun konsensus terpisah untuk setiap transaksi
Namun jika tujuannya adalah mendistribusikan demi throughput, pendekatan yang hanya membutuhkan satu leader bisa lebih efisien daripada kuorum yang diwajibkan Paxos
Ini memang hanya dugaan
Paxos juga lebih efisien jika setiap pemanggilan selalu menuju tempat yang sama
Karena kontensi dan pemungutan suara ulang dapat dihindari
Pada dasarnya, setiap shard memiliki konsensus Paxos-nya sendiri